Describe the feature
The first B-tree implementation is naive: https://github.com/vlang/v/blob/master/vlib/datatypes/btree.v
B-trees in efficient implementations use a fixed page size (each page can hold as many keys as they can fit, so there's no maximum degree).
What is relevant is then not how many keys are in each page, but how much space they take in the page. Usually this is defined as a "fill factor" (on common SQL databases, this fill factor by default is a bout 85%, but this can be tuned, and with some instrumentation such as frequency of accesses and availability of parent pages within the page caches, they can be automatically compacted to satisfy a better fill threshold, to maximize the locality, unless there are too frequent/recent accesses where constant page reorganisations by insertions/deletions may slow down the implementation).
As well the current implementation manages the leaf nodes exactly with the same underlying type as parent pages, with extra space used for a flag and nil child pointers. This is wasteful. Better implementation differentiate the root node, the intermediate parent nodes, and the leef nodes. As well, the approach using fill factors rather than degree is better.
Another optimization used in efficient B-trees for "large" types, such as strings or blobs is to avoid storing the common prefix which is alerady stored in parent nodes: this allows storing many more keys in children of leaf pages. This is commonly used in SQL databases for their indexes, to significantly improve the throughput and locality.
A variant of such indexes uses common suffixes (keys can be simply stored in reverse binary encoding order, this is converted almost transparently when retrieving keys from the store backend). So the same technic can be used as with prefixes: this is very helpful for example to create large indexes of email addresses or domain names, e.g. to implement efficient security filters.
Another variant uses data compression on keys, but is much harder to implement, notably for reorganizing trees in case of insertion (splitting subtrees), or deletion (merging subtrees), as it requires upding the parent pages (modifying their local storage for keys) and possibly other sibling pages.
Which variants of B-trees will you allow (possibly instrumented ones with statistics including on their own page caches)?
Use Case
Efficient SQL indexes, instrumentation and dynamic tuning to minimize I/O, and maximize data locality.
Proposed Solution
No response
Other Information
Note: a fixed page size does not mean that there's a maximum key size (the extra storage can fit in specific leaf pages, or could link to the flattened version of the key, possibly in linked external files). There's an example of this in the NTFS structure for its extension pages when not all file attributes (including contents, metadata, security attributes, extended attributres, or alternate data streams) can fit in the same MFT entry (whose size is limited to 1KB or 4KB: the extension is stored in a specific data stream type, whose parent header always fits in the MFT entry just after required basic properties). Similar mechanism is used in other advanced filesystems for Linux/Unix, as well as in SQL databases that accept to index "blob" types.
Note also that the page cache in not necessarily stored in CPU caches or in RAM, there may be several layers of page caches, including local file system storage (possibly with sharable memory maps, managed and coordinated with an external server-like process supporting transactions or safe journaling), before using network storage. Each layer may have its own tunable instrumentation in addition of their own page size.
Note also that in some cases it may not be possible to reorganize a parent page if it has an exclusive lock from concurrent threads or processes, so these may be delayed and the extra temporary storage to use, for what will be applied later in later steps (when the lock is released), may also used linked pages, probably coupled with a journaling system if we need support for safe transactions (and clean rollbacks or replays). Such solution can avoid extreme slowdown cases occuring in frequently modified parent or sibling pages, or to allow limiting usages and avoid time attacks on servers hosting many users or services (by using caches partitioned by security realms and management of quotas).
Acknowledgements
- I may be able to implement this feature request
- This feature might incur a breaking change
Version used
any
Environment details (OS name and version, etc.)
any
Activity
0No activity yet.