Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Re-check B-tree implementation #64

Open
jivanpal opened this issue Jan 7, 2024 · 0 comments
Open

Re-check B-tree implementation #64

jivanpal opened this issue Jan 7, 2024 · 0 comments
Labels
bug Something isn't working

Comments

@jivanpal
Copy link
Owner

jivanpal commented Jan 7, 2024

The following comment in <drat/func/btree.c> (line 318, bold emphasis mine) is false:

However, if this is the first entry in this node, we only
descend it if its key's stated OID matches the desired OID;
else it exceeds the desired OID, and thus no records with the
desired OID exist in the whole tree.

The implementation thus needs to be fixed (again...) For non-leaf nodes, consider scanning the nodes in reverse instead, from largest to smallest (OID, XID) pair, then descend the first entry we see whose (OID, XID) is less than the desired (OID, XID). Doing this should get us to the leaf node that contains the first record we're looking for.

Also consider using binary search on each node rather than linear search. Get it working with linear search first, though!

@jivanpal jivanpal added the bug Something isn't working label Jan 7, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working
Projects
Status: Backlog
Development

No branches or pull requests

1 participant