orientechnologies / orientechnologies/orientdb
Prefix B-Trees
Nobody has claimed this yet.
- Dominant language
- Java
- Stars
- 5k
- Forks
- 868
- Avg merge
- 15h 6m
- Merged PRs (30d)
- 18
Description
Currently, when we keep keys in parent pages of B-Tree we always keep full keys. But in reality, we do not need it.
Let suppose that we filled a page of B-Tree and need to split it. So we will choose key which will serve as a separator between two keys. Instead of passing full key in the parent page, we can use only part of the key which is for sure larger than all keys on the left side from the key separator. This will also ensure that this partial key is lower than all the keys from the right side of the key separator.
Because this process recursive by its nature parent pages will consume much less space than leaf pages which will allow efficiently cache them.
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
No files, tests, or entry points are named. Start by locating the B-tree page implementation and its page-splitting logic; done means parent pages store separator prefixes that remain ordered and distinguish all keys on the two child sides while preserving lookup behavior.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- databases, performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 18/100