[SERVER-2732] btreebuilder may create a bucket with a null nextLoc Created: 10/Mar/11  Updated: 25/Jul/14  Resolved: 25/Jul/14

Status: Closed
Project: Core Server
Component/s: Index Maintenance
Affects Version/s: None
Fix Version/s: None

Type: Bug Priority: Minor - P4
Reporter: Aaron Staple Assignee: Unassigned
Resolution: Duplicate Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Duplicate
is duplicated by SERVER-14584 BtreeLogic::Builder generates an inva... Closed
Operating System: ALL
Participants:

 Description   

With a constrained key size, this will happen infrequently. But it makes new btrees behave a bit like legacy btrees in some cases, so we might need to address if we adopt stricter btree structure rules. Might also make sense to spend a bit of time validating that noncompliance with the requirements for new trees does not spread as a result of different btree operations.



 Comments   
Comment by Aaron Staple [ 19/Nov/12 ]

There is a case where the null nextChild cases described above can cause the btree deletion code to mark a node "unused" which would normally only happen in legacy btrees per this comment on BtreeBucket::deleteInternalKey:

     * NOTE on legacy btree structures:
     * In legacy btrees, k' can be a nonleaf.  In such a case we 'delete' k by
     * marking it as an unused node rather than replacing it with k'.  Also, k'
     * may be a leaf but marked as an unused node.  In such a case we replace
     * k by k', preserving the key's unused marking.  This function is only
     * expected to mark a key as unused when handling a legacy btree.

The case is when the root has a null nextChild (meaning the highest ordered key in the tree has no right child) and the second highest ordered key in the tree has a left child but no right child.

      [ a, b, ..., z ]
       /  /       / \
     []  []  [x,y]   null
             / / \
           [] []  null

Where [] represents a bucket with some contents and null is a null disk loc reference.

If the 'z' key is deleted above, it cannot be replaced with 'y' per the normal btree internal key deletion algorithm because 'y' is not a leaf. Instead, 'z' is marked as an unused node.

Comment by Aaron Staple [ 19/Nov/12 ]

More detail on the above:

The way the loop in BtreeBuilder::buildNextLevel sets nextChild on internal nodes is to call popBack(). This is not called on the root.

The issue of uneven heights may happen here, where the next child of a node that will be deleted is promoted one level higher in the tree:

                DiskLoc keepLoc = keepX ? xloc : x->nextChild;
 
                if ( ! up->_pushBack(r, k, ordering, keepLoc) ) {

Now, if x is a leaf and keepX is false (I think it would have to be the rightmost leaf) a null right child will be promoted to a non leaf node.

Comment by Aaron Staple [ 15/Mar/11 ]

Just to add another detail - the leaves of trees created by btreebuilder may not all be the same height (though the vast majority will be the same height.)

Comment by Aaron Staple [ 11/Mar/11 ]

In particular it looks like the root will not have a nextChild, and in some cases when a level has just one entry in a bucket a null nextChild is assigned.

Generated at Thu Feb 08 03:01:02 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.