Work at SourceForge, help us to make it a better place! We have an immediate need for a Support Technician in our San Francisco or Denver office.

Close

Monotonic keys in BTree

mpinl
2005-08-24
2013-06-03
  • 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.

    Thanks

     
    • 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.

      alex