How to do a B*Tree insert:

add_to_page(cursor, data, ptr){
  if( data_fits_on_page ){ add data to page; return; }
  if( page==root ){
     split currentpage+(data+ptr) into lowerpart, center, upperpart
     newpage1 = lowerpart;
     newpage2 = upperpart;
     page = ptr(newpage1) + center + ptr(newpage2);
     return;
  }
  if( move_some_data_left || move_some_data_right ){
    add data to page
    return
  }
  split currentpage+(data+ptr) into lowerpart, center, upperpart
  newpage = upperpart
  currentpage = lowerpart
  pop cursor one level
  add_to_page(cursor, center, ptr(newpage));
}

unlink_entry(cursor, olddata){
  if( !is_a_leaf ){
    n = next_entry()
    if( n fits pageof(cursor) ){
      if( olddata!=nil ) copy dataof(cursor) into olddata
      copy dataof(n) into dataof(cursor)


      unlink_entry(n, nil)
      return
    }
    n = prev_entry()
    if( n fits pageof(cursor) ){
      if( olddata!=nil ) copy dataof(cursor) into olddata
      copy dataof(n) into dataof(cursor)
      unlink_entry(n, nil)
      return
    }
    unlink_entry(n, leafdata)

    move cursor data and ptr into olddata, oldptr
    add_to_page(cursor, leafdata, oldptr)

    return
  }



























  move cursor data into olddata
  if( !underfull(pageof(cursor)) ) return








}

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.3 2001/04/29 23:32:56 drh Exp $
*/
#include "sqliteInt.h"
#include "pager.h"
#include "btree.h"
#include <assert.h>

typedef unsigned int u32;











/*
** 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







/*
** 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
................................................................................
** 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
*/

















/*
** 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
................................................................................
**       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-12)/20)

/*
** 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 elements 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;













/*
** 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 */
};


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



*/
static void useSpace(MemPage *pPage, int start, int size){
  int i;
  FreeBlk *p;


  /* Some basic sanity checking */
  assert( pPage && pPage->isInit );
  assert( pPage->nFree>0 && pPage->nFree<=MX_FREE );
  assert( pPage->nFreeSlot >= size );
  assert( start > pPage->idxStart );
  assert( size>0 );
  assert( start + size < SQLITE_PAGE_SIZE/sizeof(pPage->aPage[0]) );

  /* Search for the freeblock that describes the space to be used */
  for(i=0; i<pPage->nFree; i++){
    p = &pPage->aFree[i]
    if( p->idx<=start && p->idx+p->size>start ) break;
  }

  /* The freeblock must contain all the space that is to be used */
  assert( i<pPage->nFree );
  assert( p->idx+p->size >= start+size );

  /* Remove the used space from the freeblock */
  if( p->idx==start ){
    /* The space is at the beginning of the block
    p->size -= size;
    if( p->size==0 ){
      *p = pPage->aFree[pPage->nFree-1];
      pPage->nFree--;
    }
  }else if( p->idx+p->size==start+size ){
    /* Space at the end of the block */
    p->size -= size;
  }else{
    /* Space in the middle of the freeblock. */
    FreeBlk *pNew;
    assert( p->nFreeSlot < MX_FREE );
    pNew->idx = start+size;
    pNew->size = p->idx+p->size - pNew->idx;
    p->size = start - p->idx;
  }
  pPage->nFreeSlot -= size;
}

/*
** Return a section of the MemPage.aPage[] to the freelist.

*/
static void freeSpace(MemPage *pPage, int start, int size){
  int end = start+size;
  int i;
  FreeBlk *pMatch = 0;
  FreeBlk *
  for(i=0; i<pPage->nFreeSlot; i++){
    FreeBlk *p = &pPage->aFree[i];
    if( p->idx==end+1 ){
      if( pMatch ){
        
      }else{
        p->idx = start;
        p->size += size;
        pMatch = p;
      }
    }
    if( p->idx+p->size+1==start ){
      p->size += size;
      break;
    }
  }
}

/*
** Defragment the freespace

*/
static void defragmentSpace(MemPage *pPage){
}

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

** 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
................................................................................
** 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
................................................................................
**       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;