im-rs icon indicating copy to clipboard operation
im-rs copied to clipboard

Fix a bug in BTree get_next and get_prev search

Open rphmeier opened this issue 1 year ago • 0 comments

Closes #215

Previously, we weren't accounting for separator keys correctly in the recursive search. This commit fixes that and adds property tests.

For example, if the root node had a separator with key 66 and the right child node had keys [68, 69, 70, ...], a call to lookup_prev(67) would recurse into the child, find that there is nothing less than or equal to 67, and then bubble up a None value all the way. The correct behavior is to return 66 from the parent node.

The changeset here amends the search to return the previous separator when searching a child returns None.

rphmeier avatar Nov 01 '24 20:11 rphmeier