SQLite

How to do a B*Tree insert:

add_to_page(pageptr, data, pgno){
  pgno.parent = pageptr
  if( data+pgno fits on pageptr ){
    add data+pgno to pageptr
    return
  }
  if( pageptr==root ){

    split pageptr+(data+pgno) into newpage1, center, newpage2

    pageptr = ptr(newpage1) + center + ptr(newpage2);
    return
  }
  if( move_some_data_left || move_some_data_right ){
    add data+pgno to pageptr
    return
  }
  split pageptr+(data+pgno) into pageptr, center, newpage
  add_to_page(parent(pageptr), center, ptr(newpage));
  newpage.parent = parent(pageptr)
}

Cursor: pageptr, idx

unlink_entry(cursor, olddata){
  if( cursor.pageptr is not a leaf page ){
    if( olddata!=nil) copy payload(cursor) into olddata
    n = next_entry(cursor)
    if( payloadsize(n) <= freesize(cursor) + payloadsize(cursor) ){
      copy payload(n) into payload(cursor)
      unlink_entry(n, nil)
      return
    }
    p = prev_entry(cursor)
    if( payloadsize(p) <= freesize(cursor) + payloadsize(cursor) ){
      copy payload(p) into payload(cursor)
      unlink_entry(p, nil)
      return
    }
    unlink(n, leafdata)
    pageptr = cursor.pageptr
    nextpgno = pageptr.aCell[cursor.idx].pgno;
    convert_cursor_to_free_block(cursor)
    add_to_page(pageptr, leafdata, nextpgno)
    return
  }
  pageptr = cursor.pageptr;
  convert_cursor_to_free_block(cursor)
  if( usage(pageptr)<0.65 ){
    consolidate(pageptr)
  }
}

consolidate(pageptr){
  parentpage = parentof(pageptr)
  idx = index_of_page(parentpage, pageptr);
  leftsibling = parentpage.cell[idx].pgno;
  rightsibling = parentpage.cell[idx+1].pgno;
  if( idx>0 ){
    cursor = makecursor(pageptr,idx-1)
    if( try_to_move_down(cursor) ) return
  }

  if( idx<max ){

    cursor = makecursor(pageptr,idx)

    try_to_move_down(cursor)

  }
  return
}

try_to_move_down(cursor){
  pageptr = cursor.pageptr
  if( payload(cursor)+sizeof(left)+sizeof(right)<=pagesize ){
    put cursor and content of left into right
    remove cursor from pageptr
    if( pageptr is root ){
      if( cellcount(pageptr)==0 ){
        copy child into pageptr
        update parent field of child
      }
    }else if( usage(pageptr)<0.65 ){
      try_to_move_down(cursor)
    }
  }
}

cursor_move_next(cursor){
  if( cursor.incr_noop ){
    cursor.incr_noop = FALSE;
    return;
  }
  if( is_leaf(cursor.pageptr) ){
    if( cursor.idx==cursor.pageptr.ncell ){
      if( cursor.pageptr==root ){
        nil cursor
        return
      }
      cursor_move_up(cursor)
      cursor_move_next(cursor)
    }else{
      cursor.idx++;
    }
    return
  }
  pgno = next_pgno(cursor)
  loop {
    cursor.pageptr = get(pgno);
    if( is_leaf(cursor.pageptr) ) break;
    pgno = first_pgno(pageptr);
  }
  cursor.idx = 0;
}

** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*************************************************************************
** $Id: btree.c,v 1.4 2001/05/11 11:02:47 drh Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include <assert.h>

typedef unsigned int u32;
typedef unsigned short int u16;

/*
** Forward declarations of structures used only in this file.
*/
typedef struct Page1Header Page1Header;
typedef struct PageHdr PageHdr;
typedef struct Cell Cell;
typedef struct FreeBlk FreeBlk;


/*
** The first page contains the following additional information:
**
**      MAGIC-1
**      MAGIC-2
**      First free block
*/
#define EXTRA_PAGE_1_CELLS  3
#define MAGIC_1  0x7264dc61
#define MAGIC_2  0x54e55d9e

struct Page1Header {
  u32 magic1;
  u32 magic2;
  Pgno firstList;
};

/*
** Each database page has a header as follows:
**
**      page1_header          Extra numbers found on page 1 only.
**      leftmost_pgno         Page number of the leftmost child
**      first_cell            Index into MemPage.aPage of first cell
**      first_free            Index of first free block
**
** MemPage.pStart always points to the leftmost_pgno.  First_free is
** 0 if there is no free space on this page.  Otherwise it points to
** an area like this:
**
**      nByte                 Number of free bytes in this block
**      next_free             Next free block or 0 if this is the end
*/
struct PageHdr {
  Pgno pgno;      /* Child page that comes after all cells on this page */
  u16 firstCell;  /* Index in MemPage.aPage[] of the first cell */
  u16 firstFree;  /* Index in MemPage.aPage[] of the first free block */
};
struct Cell {
  Pgno pgno;      /* Child page that comes before this cell */
  u16 nKey;       /* Number of bytes in the key */
  u16 iNext;      /* Index in MemPage.aPage[] of next cell in sorted order */
  u32 nData;      /* Number of bytes of data */
  char aData[4];  /* Key and data */
};
struct FreeBlk {
  u16 iSize;      /* Number of u32-sized slots in the block of free space */
  u16 iNext;      /* Index in MemPage.aPage[] of the next free block */
};

/*
** The maximum number of database entries that can be held in a single
** page of the database.  Each entry has a 16-byte header consisting of
** 4 unsigned 32-bit numbers, as follows:
**
**       nKey       Number of byte in the key
**       nData      Number of byte in the data
**       pgno       Page number of the right child block 
**       next       index in MemPage.aPage[] of the next entry in sorted order
**
** The key and data follow this header.  The key and data are packed together
** and the total rounded up to the next multiple of 4 bytes.  There must
** be at least 4 bytes in the key/data packet, so each entry consumes at
** least 20 bytes of space on the page.
*/
#define MX_CELL ((SQLITE_PAGE_SIZE-sizeof(PageHdr))/sizeof(Cell))

/*
** The maximum amount of data (in bytes) that can be stored locally for a
** database entry.  If the entry contains more data than this, the
** extra goes onto overflow pages.
*/
#define MX_LOCAL_PAYLOAD ((SQLITE_PAGE_SIZE-20-4*24)/4)

  unsigned char validUp;                    /* True if MemPage.up is valid */
  unsigned char validLeft;                  /* True if MemPage.left is valid */
  unsigned char validRight;                 /* True if MemPage.right is valid */
  Pgno up;                     /* The parent page.  0 means this is the root */
  Pgno left;                   /* Left sibling page.  0==none */
  Pgno right;                  /* Right sibling page.  0==none */
  int idxStart;                /* Index in aPage[] of real data */
  int nFree;                   /* Number of free slots of aPage[] */
  int nCell;                   /* Number of entries on this page */
  u32 *aCell[MX_CELL];         /* All entires in sorted order */
}
typedef struct MemPage;

/*
** The in-memory image of a disk page has the auxiliary information appended

  Pager *pPager;        /* The page cache */
  BtCursor *pCursor;    /* All open cursors */
  MemPage *page1;       /* First page of the database */
  int inTrans;          /* True if a transaction is current */
};
typedef Btree Bt;

/*
** A cursor is a pointer to a particular entry in the BTree.
** The entry is identified by its MemPage and the index in
** MemPage.aCell[] of the entry.
*/
struct Cursor {
  Btree *pBt;           /* The pointer back to the BTree */
  MemPage *pPage;       /* Page that contains the entry */
  int idx;              /* Index of the entry in pPage->aCell[] */
  int skip_incr;        /* */
};

/*
** The maximum depth of a cursor
*/
#define MX_LEVEL 20

/*

  BtCursor *pPrev, *pNext;      /* Linked list of all cursors */
  int valid;                    /* True if the cursor points to something */
  int nLevel;                   /* Number of levels of indexing used */
  BtIdxpt *pLevel;              /* Pointer to aLevel[nLevel] */
  BtIdxpt aLevel[MX_LEVEL];     /* The index levels */
};


/*
** Defragment the page given.  All of the free space
** is collected into one big block at the end of the
** page.
*/



static void defragmentPage(MemPage *pPage){







}





/*
** Mark a section of the memory block as in-use.


*/






static void useSpace(MemPage *pPage, int start, int size){













}

/*
** Return a section of the MemPage.aPage[] to the freelist.
*/
static void freeSpace(MemPage *pPage, int start, int size){


























}

/*
** Initialize the auxiliary information for a disk block.
*/
static int initPage(MemPage *pPage, Pgno pgnoThis, Pgno pgnoParent){
  u32 idx;