Monotonic keys in BTree

  • mpinl

    mpinl - 2005-08-24

    Hi there

    During my work on adding the ability to efficiently store monotonic increasing keys in a BTree (by allowing the user to manually define the splitting point), I used BTree.dump() to output the structure.
    Then I wondered why when creating very small trees there was no output at all. I thought that something did go terribly wrong, but the cause was the line
         if ( _keys[ i ] == null ) break;
    in BPage.dumpRecursive (about line #902). It "forgets" to output the last page in the BTree. If I comment this line, the last page is dumped as well. Then I searched the error in my implementation, but didn't find anything.

    Thus I returned to the current 1.0 release, and there it was the same. When using the current release, the first entry of the last page is always NULL (after inserting monotonic increasing keys). (The first entry is the last of the keys/children/objects-arrays as they're filled starting at the last position.)

    When using a TupleBrowser to dump the tree (like in FamousPeople), all tuples are output though. So, is this

    - a bug in the current BTree-implementation (in my optionion it's at least a little odd)
    - a bug in dumpRecursive()

    Can anyone reproduce this? My tests consist of a BTree with pageSize 64 and 600 added keys.


    • Alex Boisvert

      Alex Boisvert - 2005-08-24

      Yes, it was a bug in dumpRecursive().  I should have used the _children field instead of _key to determine if there's an underlying object/page.

      It's now fixed in CVS.



Log in to post a comment.