[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: |
|
||||||||
| 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:
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.
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:
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. |