Make bt_splitpage more conservative wrt posting fence keys

diff --git a/btree2s.c b/btree2s.c
index 586dea7c2034183cdc5b8164ae4039be7e13a9eb..49b910961e8240139eabe622717f61a2f2daab0b 100644 (file)
--- a/btree2s.c
+++ b/btree2s.c
@@ -121,10 +121,9 @@ typedef struct {
        uint min;                                       // next key offset
        unsigned char bits:7;           // page size in bits
        unsigned char free:1;           // page is on free list
        uint min;                                       // next key offset
        unsigned char bits:7;           // page size in bits
        unsigned char free:1;           // page is on free list

-       unsigned char lvl:5;            // level of page
+       unsigned char lvl:6;            // level of page

        unsigned char kill:1;           // page is being deleted
        unsigned char dirty:1;          // page is dirty
        unsigned char kill:1;           // page is being deleted
        unsigned char dirty:1;          // page is dirty

-       unsigned char posted:1;         // page is posted in parent

        unsigned char right[BtId];      // page number to right
 } *BtPage;
 
        unsigned char right[BtId];      // page number to right
 } *BtPage;
 


@@ -1500,11 +1499,10 @@ uid right;
 BTERR bt_splitpage (BtDb *bt)
 {
 uint cnt = 0, idx = 0, max, nxt = bt->page_size;
 BTERR bt_splitpage (BtDb *bt)
 {
 uint cnt = 0, idx = 0, max, nxt = bt->page_size;

+unsigned char fencekey[256], rightkey[256];

 uid page_no = bt->page_no, right;
 uid page_no = bt->page_no, right;

-unsigned char fencekey[256];

 BtPage page = bt->page;
 uint lvl = page->lvl;
 BtPage page = bt->page;
 uint lvl = page->lvl;

-uint prev;

 BtKey key;
 
        //  split higher half of keys to bt->frame
 BtKey key;
 
        //  split higher half of keys to bt->frame


@@ -1526,6 +1524,10 @@ BtKey key;
                slotptr(bt->frame, idx)->off = nxt;
        }
 
                slotptr(bt->frame, idx)->off = nxt;
        }
 

+       //      remember fence key for new right page
+
+       memcpy (rightkey, key, key->len + 1);
+

        bt->frame->bits = bt->page_bits;
        bt->frame->min = nxt;
        bt->frame->cnt = idx;
        bt->frame->bits = bt->page_bits;
        bt->frame->min = nxt;
        bt->frame->cnt = idx;


@@ -1546,7 +1548,6 @@ BtKey key;
        memcpy (bt->frame, page, bt->page_size);
        memset (page+1, 0, bt->page_size - sizeof(*page));
        nxt = bt->page_size;
        memcpy (bt->frame, page, bt->page_size);
        memset (page+1, 0, bt->page_size - sizeof(*page));
        nxt = bt->page_size;

-       page->posted = 0;

        page->dirty = 0;
        page->act = 0;
        cnt = 0;
        page->dirty = 0;
        page->act = 0;
        cnt = 0;


@@ -1568,6 +1569,7 @@ BtKey key;
        // remember fence key for smaller page
 
        memcpy (fencekey, key, key->len + 1);
        // remember fence key for smaller page
 
        memcpy (fencekey, key, key->len + 1);

+

        bt_putid(page->right, right);
        page->min = nxt;
        page->cnt = idx;
        bt_putid(page->right, right);
        page->min = nxt;
        page->cnt = idx;


@@ -1577,59 +1579,33 @@ BtKey key;
        if( page_no == ROOT_page )
                return bt_splitroot (bt, fencekey, right);
 
        if( page_no == ROOT_page )
                return bt_splitroot (bt, fencekey, right);
 

-       // update left (containing) node
+       //      lock right page

 
 

-       if( bt_update(bt, page, page_no) )
+       if( bt_lockpage (bt, right, BtLockParent) )

                return bt->err;
 
                return bt->err;
 

-       right = 0;
-
-       //  insert new fences in parent pages
+       // update left (containing) node

 
 

-       while( 1 ) {
-         if( bt_lockpage (bt, page_no, BtLockParent) )
+       if( bt_update(bt, page, page_no) )

                return bt->err;
 
                return bt->err;
 

-         if( right )
-          if( bt_mappage (bt, &bt->page, page_no) )
+       if( bt_lockpage (bt, page_no, BtLockParent) )

                return bt->err;
 
                return bt->err;
 

-         key = keyptr(bt->page, bt->page->cnt);
-         memcpy (fencekey, key, key->len + 1);
-         prev = bt->page->posted;
-
-         if( right && prev ) {
-               if( bt_unlockpage (bt, page_no, BtLockParent) )
-                 return bt->err;
-               return bt_unlockpage (bt, page_no, BtLockWrite);
-         }
-
-         right = bt_getid (bt->page->right);
-         bt->page->posted = 1;
+       // insert new fence for reformulated left block

 
 

-         if( bt_update (bt, bt->page, page_no) )
+       if( bt_insertkey (bt, fencekey+1, *fencekey, lvl+1, page_no, time(NULL)) )

                return bt->err;
 
                return bt->err;
 

-         if( bt_unlockpage (bt, page_no, BtLockWrite) )
-               return bt->err;
-
-         // insert new fence for reformulated left block
-
-         if( !prev )
-          if( bt_insertkey (bt, fencekey+1, *fencekey, lvl + 1, page_no, time(NULL)) )
-               return bt->err;
+       //      switch fence for right block of larger keys to new right page

 
 

-         if( bt_unlockpage (bt, page_no, BtLockParent) )
+       if( bt_insertkey (bt, rightkey+1, *rightkey, lvl+1, right, time(NULL)) )

                return bt->err;
 
                return bt->err;
 

-         if( !(page_no = right) )
-               break;
-
-         if( bt_lockpage (bt, page_no, BtLockWrite) )
+       if( bt_unlockpage (bt, page_no, BtLockParent) )

                return bt->err;
                return bt->err;

-       }

 
 

-       return 0;
+       return bt_unlockpage (bt, right, BtLockParent);

 }
 
 //  Insert new key into the btree at requested level.
 }
 
 //  Insert new key into the btree at requested level.

diff --git a/threads2h.c b/threads2h.c
index 46742c487497d05185dd795028a54aadb46ff4db..4a28044811ef815c490558f5cf66af89d13c29aa 100644 (file)
--- a/threads2h.c
+++ b/threads2h.c
@@ -170,10 +170,9 @@ typedef struct BtPage_ {
        uint min;                                       // next key offset
        unsigned char bits:7;           // page size in bits
        unsigned char free:1;           // page is on free list
        uint min;                                       // next key offset
        unsigned char bits:7;           // page size in bits
        unsigned char free:1;           // page is on free list

-       unsigned char lvl:5;            // level of page
+       unsigned char lvl:6;            // level of page

        unsigned char kill:1;           // page is being killed
        unsigned char dirty:1;          // page has deleted keys
        unsigned char kill:1;           // page is being killed
        unsigned char dirty:1;          // page has deleted keys

-       unsigned char posted:1;         // page fence is posted

        unsigned char right[BtId];      // page number to right
 } *BtPage;
 
        unsigned char right[BtId];      // page number to right
 } *BtPage;
 


@@ -1964,10 +1963,10 @@ uid left;
 BTERR bt_splitpage (BtDb *bt, BtPageSet *set)
 {
 uint cnt = 0, idx = 0, max, nxt = bt->mgr->page_size;
 BTERR bt_splitpage (BtDb *bt, BtPageSet *set)
 {
 uint cnt = 0, idx = 0, max, nxt = bt->mgr->page_size;

-unsigned char fencekey[256];
+unsigned char fencekey[256], rightkey[256];

 uint lvl = set->page->lvl;
 uint lvl = set->page->lvl;

+BtPageSet right[1];

 uint prev;
 uint prev;

-uid right;

 BtKey key;
 
        //  split higher half of keys to bt->frame
 BtKey key;
 
        //  split higher half of keys to bt->frame


@@ -1989,6 +1988,10 @@ BtKey key;
                slotptr(bt->frame, idx)->off = nxt;
        }
 
                slotptr(bt->frame, idx)->off = nxt;
        }
 

+       // remember existing fence key for new page to the right
+
+       memcpy (rightkey, key, key->len + 1);
+

        bt->frame->bits = bt->mgr->page_bits;
        bt->frame->min = nxt;
        bt->frame->cnt = idx;
        bt->frame->bits = bt->mgr->page_bits;
        bt->frame->min = nxt;
        bt->frame->cnt = idx;


@@ -2001,7 +2004,7 @@ BtKey key;
 
        //      get new free page and write higher keys to it.
 
 
        //      get new free page and write higher keys to it.
 

-       if( !(right = bt_newpage(bt, bt->frame)) )
+       if( !(right->page_no = bt_newpage(bt, bt->frame)) )

                return bt->err;
 
        //      update lower keys to continue in old page
                return bt->err;
 
        //      update lower keys to continue in old page


@@ -2009,7 +2012,6 @@ BtKey key;
        memcpy (bt->frame, set->page, bt->mgr->page_size);
        memset (set->page+1, 0, bt->mgr->page_size - sizeof(*set->page));
        nxt = bt->mgr->page_size;
        memcpy (bt->frame, set->page, bt->mgr->page_size);
        memset (set->page+1, 0, bt->mgr->page_size - sizeof(*set->page));
        nxt = bt->mgr->page_size;

-       set->page->posted = 0;

        set->page->dirty = 0;
        set->page->act = 0;
        cnt = 0;
        set->page->dirty = 0;
        set->page->act = 0;
        cnt = 0;


@@ -2030,62 +2032,40 @@ BtKey key;
        // remember fence key for smaller page
 
        memcpy(fencekey, key, key->len + 1);
        // remember fence key for smaller page
 
        memcpy(fencekey, key, key->len + 1);

-       bt_putid(set->page->right, right);
+
+       bt_putid(set->page->right, right->page_no);

        set->page->min = nxt;
        set->page->cnt = idx;
 
        // if current page is the root page, split it
 
        if( set->page_no == ROOT_page )
        set->page->min = nxt;
        set->page->cnt = idx;
 
        // if current page is the root page, split it
 
        if( set->page_no == ROOT_page )

-               return bt_splitroot (bt, set, fencekey, right);
-
-       right = 0;
+               return bt_splitroot (bt, set, fencekey, right->page_no);

 
        // insert new fences in their parent pages
 
 
        // insert new fences in their parent pages
 

-       while( 1 ) {
-               bt_lockpage (BtLockParent, set->latch);
-
-               key = keyptr (set->page, set->page->cnt);
-               memcpy (fencekey, key, key->len + 1);
-               prev = set->page->posted;
-
-               if( right && prev ) {
-                       bt_unlockpage (BtLockParent, set->latch);
-                       bt_unlockpage (BtLockWrite, set->latch);
-                       bt_unpinlatch (set->latch);
-                       bt_unpinpool (set->pool);
-                       return 0;
-               }
-
-               right = bt_getid (set->page->right);
-               set->page->posted = 1;
-
-               bt_unlockpage (BtLockWrite, set->latch);
-
-               // insert new fence for reformulated left block of smaller keys
+       right->latch = bt_pinlatch (bt, right->page_no);
+       bt_lockpage (BtLockParent, right->latch);

 
 

-               if( !prev )
-                 if( bt_insertkey (bt, fencekey+1, *fencekey, lvl+1, set->page_no, time(NULL)) )
-                       return bt->err;
+       bt_lockpage (BtLockParent, set->latch);
+       bt_unlockpage (BtLockWrite, set->latch);

 
 

-               bt_unlockpage (BtLockParent, set->latch);
-               bt_unpinlatch (set->latch);
-               bt_unpinpool (set->pool);
+       // insert new fence for reformulated left block of smaller keys

 
 

-               if( !(set->page_no = right) )
-                       break;
+       if( bt_insertkey (bt, fencekey+1, *fencekey, lvl+1, set->page_no, time(NULL)) )
+               return bt->err;

 
 

-               set->latch = bt_pinlatch (bt, right);
+       // switch fence for right block of larger keys to new right page

 
 

-               if( set->pool = bt_pinpool (bt, right) )
-                       set->page = bt_page (bt, set->pool, right);
-               else
-                       return bt->err;
+       if( bt_insertkey (bt, rightkey+1, *rightkey, lvl+1, right->page_no, time(NULL)) )
+               return bt->err;

 
 

-               bt_lockpage (BtLockWrite, set->latch);
-       }
+       bt_unlockpage (BtLockParent, set->latch);
+       bt_unpinlatch (set->latch);
+       bt_unpinpool (set->pool);

 
 

+       bt_unlockpage (BtLockParent, right->latch);
+       bt_unpinlatch (right->latch);

        return 0;
 }
 
        return 0;
 }
 

diff --git a/threads2i.c b/threads2i.c
index 0c7c41d43896023485e29cab0f96a3ad30b640c9..c425d1813601f9c3c0f2eef029d67b93e9104ac4 100644 (file)
--- a/threads2i.c
+++ b/threads2i.c
@@ -1878,10 +1878,10 @@ uid left;
 BTERR bt_splitpage (BtDb *bt, BtPageSet *set)
 {
 uint cnt = 0, idx = 0, max, nxt = bt->mgr->page_size;
 BTERR bt_splitpage (BtDb *bt, BtPageSet *set)
 {
 uint cnt = 0, idx = 0, max, nxt = bt->mgr->page_size;

-unsigned char fencekey[256];
+unsigned char fencekey[256], rightkey[256];

 uint lvl = set->page->lvl;
 uint lvl = set->page->lvl;

+BtPageSet right[1];

 uint prev;
 uint prev;

-uid right;

 BtKey key;
 
        //  split higher half of keys to bt->frame
 BtKey key;
 
        //  split higher half of keys to bt->frame


@@ -1903,6 +1903,10 @@ BtKey key;
                slotptr(bt->frame, idx)->off = nxt;
        }
 
                slotptr(bt->frame, idx)->off = nxt;
        }
 

+       // remember existing fence key for new page to the right
+
+       memcpy (rightkey, key, key->len + 1);
+

        bt->frame->bits = bt->mgr->page_bits;
        bt->frame->min = nxt;
        bt->frame->cnt = idx;
        bt->frame->bits = bt->mgr->page_bits;
        bt->frame->min = nxt;
        bt->frame->cnt = idx;


@@ -1915,7 +1919,7 @@ BtKey key;
 
        //      get new free page and write higher keys to it.
 
 
        //      get new free page and write higher keys to it.
 

-       if( !(right = bt_newpage(bt, bt->frame)) )
+       if( !(right->page_no = bt_newpage(bt, bt->frame)) )

                return bt->err;
 
        //      update lower keys to continue in old page
                return bt->err;
 
        //      update lower keys to continue in old page


@@ -1923,7 +1927,6 @@ BtKey key;
        memcpy (bt->frame, set->page, bt->mgr->page_size);
        memset (set->page+1, 0, bt->mgr->page_size - sizeof(*set->page));
        nxt = bt->mgr->page_size;
        memcpy (bt->frame, set->page, bt->mgr->page_size);
        memset (set->page+1, 0, bt->mgr->page_size - sizeof(*set->page));
        nxt = bt->mgr->page_size;

-       set->page->posted = 0;

        set->page->dirty = 0;
        set->page->act = 0;
        cnt = 0;
        set->page->dirty = 0;
        set->page->act = 0;
        cnt = 0;


@@ -1944,65 +1947,42 @@ BtKey key;
        // remember fence key for smaller page
 
        memcpy(fencekey, key, key->len + 1);
        // remember fence key for smaller page
 
        memcpy(fencekey, key, key->len + 1);

-       bt_putid(set->page->right, right);
+
+       bt_putid(set->page->right, right->page_no);

        set->page->min = nxt;
        set->page->cnt = idx;
 
        // if current page is the root page, split it
 
        if( set->page_no == ROOT_page )
        set->page->min = nxt;
        set->page->cnt = idx;
 
        // if current page is the root page, split it
 
        if( set->page_no == ROOT_page )

-               return bt_splitroot (bt, set, fencekey, right);
-
-       right = 0;
+               return bt_splitroot (bt, set, fencekey, right->page_no);

 
        // insert new fences in their parent pages
 
 
        // insert new fences in their parent pages
 

-       while( 1 ) {
-               bt_lockpage (BtLockParent, set->latch);
-
-               key = keyptr (set->page, set->page->cnt);
-               memcpy (fencekey, key, key->len + 1);
-               prev = set->page->posted;
-
-               if( right && prev ) {
-                       bt_unlockpage (BtLockParent, set->latch);
-                       bt_unlockpage (BtLockWrite, set->latch);
-                       bt_unpinlatch (set->latch);
-                       bt_unpinpool (set->pool);
-                       return 0;
-               }
-
-               right = bt_getid (set->page->right);
-               set->page->posted = 1;
-
-               bt_unlockpage (BtLockWrite, set->latch);
-
-               // insert new fence for reformulated left block of smaller keys
+       right->latch = bt_pinlatch (bt, right->page_no);
+       bt_lockpage (BtLockParent, right->latch);

 
 

-               if( !prev )
-                 if( bt_insertkey (bt, fencekey+1, *fencekey, lvl+1, set->page_no, time(NULL)) )
-                       return bt->err;
+       bt_lockpage (BtLockParent, set->latch);
+       bt_unlockpage (BtLockWrite, set->latch);

 
 

-               bt_unlockpage (BtLockParent, set->latch);
-               bt_unpinlatch (set->latch);
-               bt_unpinpool (set->pool);
+       // insert new fence for reformulated left block of smaller keys

 
 

-               if( !(set->page_no = right) )
-                       break;
+       if( bt_insertkey (bt, fencekey+1, *fencekey, lvl+1, set->page_no, time(NULL)) )
+               return bt->err;

 
 

-               set->latch = bt_pinlatch (bt, right);
+       // switch fence for right block of larger keys to new right page

 
 

-               if( set->pool = bt_pinpool (bt, right) )
-                       set->page = bt_page (bt, set->pool, right);
-               else
-                       return bt->err;
+       if( bt_insertkey (bt, rightkey+1, *rightkey, lvl+1, right->page_no, time(NULL)) )
+               return bt->err;

 
 

-               bt_lockpage (BtLockWrite, set->latch);
-       }
+       bt_unlockpage (BtLockParent, set->latch);
+       bt_unpinlatch (set->latch);
+       bt_unpinpool (set->pool);

 
 

+       bt_unlockpage (BtLockParent, right->latch);
+       bt_unpinlatch (right->latch);

        return 0;
 }
        return 0;
 }

-

 //  Insert new key into the btree at given level.
 
 BTERR bt_insertkey (BtDb *bt, unsigned char *key, uint len, uint lvl, uid id, uint tod)
 //  Insert new key into the btree at given level.
 
 BTERR bt_insertkey (BtDb *bt, unsigned char *key, uint len, uint lvl, uid id, uint tod)

diff --git a/threads2j.c b/threads2j.c
index ce186a60b2e52fb3c1150bfd03b081b5f02a6575..a1081b33ed78e104815d37e7285c4d68e0c79163 100644 (file)
--- a/threads2j.c
+++ b/threads2j.c
@@ -1926,11 +1926,11 @@ uid left;
 BTERR bt_splitpage (BtDb *bt, BtPageSet *set)
 {
 uint cnt = 0, idx = 0, max, nxt = bt->mgr->page_size;
 BTERR bt_splitpage (BtDb *bt, BtPageSet *set)
 {
 uint cnt = 0, idx = 0, max, nxt = bt->mgr->page_size;

-unsigned char fencekey[256];
+unsigned char fencekey[256], rightkey[256];

 uint lvl = set->page->lvl;
 uint lvl = set->page->lvl;

-uid right;
-BtKey key;
+BtPageSet right[1];

 uint prev;
 uint prev;

+BtKey key;

 
        //  split higher half of keys to bt->frame
 
 
        //  split higher half of keys to bt->frame
 


@@ -1951,6 +1951,10 @@ uint prev;
                slotptr(bt->frame, idx)->off = nxt;
        }
 
                slotptr(bt->frame, idx)->off = nxt;
        }
 

+       // remember existing fence key for new page to the right
+
+       memcpy (rightkey, key, key->len + 1);
+

        bt->frame->bits = bt->mgr->page_bits;
        bt->frame->min = nxt;
        bt->frame->cnt = idx;
        bt->frame->bits = bt->mgr->page_bits;
        bt->frame->min = nxt;
        bt->frame->cnt = idx;


@@ -1963,7 +1967,7 @@ uint prev;
 
        //      get new free page and write higher keys to it.
 
 
        //      get new free page and write higher keys to it.
 

-       if( !(right = bt_newpage(bt, bt->frame)) )
+       if( !(right->page_no = bt_newpage(bt, bt->frame)) )

                return bt->err;
 
        //      update lower keys to continue in old page
                return bt->err;
 
        //      update lower keys to continue in old page


@@ -1971,7 +1975,6 @@ uint prev;
        memcpy (bt->frame, set->page, bt->mgr->page_size);
        memset (set->page+1, 0, bt->mgr->page_size - sizeof(*set->page));
        nxt = bt->mgr->page_size;
        memcpy (bt->frame, set->page, bt->mgr->page_size);
        memset (set->page+1, 0, bt->mgr->page_size - sizeof(*set->page));
        nxt = bt->mgr->page_size;

-       set->page->posted = 0;

        set->page->dirty = 0;
        set->page->act = 0;
        cnt = 0;
        set->page->dirty = 0;
        set->page->act = 0;
        cnt = 0;


@@ -1992,65 +1995,42 @@ uint prev;
        // remember fence key for smaller page
 
        memcpy(fencekey, key, key->len + 1);
        // remember fence key for smaller page
 
        memcpy(fencekey, key, key->len + 1);

-       bt_putid(set->page->right, right);
+
+       bt_putid(set->page->right, right->page_no);

        set->page->min = nxt;
        set->page->cnt = idx;
 
        // if current page is the root page, split it
 
        if( set->page_no == ROOT_page )
        set->page->min = nxt;
        set->page->cnt = idx;
 
        // if current page is the root page, split it
 
        if( set->page_no == ROOT_page )

-               return bt_splitroot (bt, set, fencekey, right);
-
-       bt_unlockpage (BtLockWrite, set->latch);
-       right = 0;
+               return bt_splitroot (bt, set, fencekey, right->page_no);

 
        // insert new fences in their parent pages
 
 
        // insert new fences in their parent pages
 

-       while( 1 ) {
-               bt_lockpage (BtLockParent, set->latch);
-               bt_lockpage (BtLockWrite, set->latch);
-
-               key = keyptr (set->page, set->page->cnt);
-               memcpy (fencekey, key, key->len + 1);
-               prev = set->page->posted;
-
-               if( right && prev ) {
-                       bt_unlockpage (BtLockParent, set->latch);
-                       bt_unlockpage (BtLockWrite, set->latch);
-                       bt_unpinlatch (set->latch);
-                       bt_unpinpool (set->pool);
-                       return 0;
-               }
-
-               right = bt_getid (set->page->right);
-               set->page->posted = 1;
-
-               bt_unlockpage (BtLockWrite, set->latch);
+       right->latch = bt_pinlatch (bt, right->page_no);
+       bt_lockpage (BtLockParent, right->latch);

 
 

-               // insert new fence for reformulated left block of smaller keys
+       bt_lockpage (BtLockParent, set->latch);
+       bt_unlockpage (BtLockWrite, set->latch);

 
 

-               if( !prev )
-                 if( bt_insertkey (bt, fencekey+1, *fencekey, lvl+1, set->page_no, time(NULL)) )
-                       return bt->err;
+       // insert new fence for reformulated left block of smaller keys

 
 

-               bt_unlockpage (BtLockParent, set->latch);
-               bt_unpinlatch (set->latch);
-               bt_unpinpool (set->pool);
+       if( bt_insertkey (bt, fencekey+1, *fencekey, lvl+1, set->page_no, time(NULL)) )
+               return bt->err;

 
 

-               if( !(set->page_no = right) )
-                       break;
+       // switch fence for right block of larger keys to new right page

 
 

-               set->latch = bt_pinlatch (bt, right);
+       if( bt_insertkey (bt, rightkey+1, *rightkey, lvl+1, right->page_no, time(NULL)) )
+               return bt->err;

 
 

-               if( set->pool = bt_pinpool (bt, right) )
-                       set->page = bt_page (bt, set->pool, right);
-               else
-                       return bt->err;
-       }
+       bt_unlockpage (BtLockParent, set->latch);
+       bt_unpinlatch (set->latch);
+       bt_unpinpool (set->pool);

 
 

+       bt_unlockpage (BtLockParent, right->latch);
+       bt_unpinlatch (right->latch);

        return 0;
 }
        return 0;
 }

-

 //  Insert new key into the btree at given level.
 
 BTERR bt_insertkey (BtDb *bt, unsigned char *key, uint len, uint lvl, uid id, uint tod)
 //  Insert new key into the btree at given level.
 
 BTERR bt_insertkey (BtDb *bt, unsigned char *key, uint len, uint lvl, uid id, uint tod)