2
$\begingroup$

In both B-trees and B+trees, a node (a.k.a page) contains K keys and K+1 pointers:

node = [ ptr_1, key_1,  ... , ptr_K , key_K , ptr_(K+1) ]

Now suppose that I want a B/B+ tree (whichever possible), where each node contains exactly K keys and K pointers, in form of {key,ptr} pairs:

node = [{key_1,ptr_1} , ... , {key_K,ptr_K}]

By aligning key-values as an array of paired structs, it will be more efficient to process key-value pairs in CPUs and use SIMD operations, etc.

It is easy to statically construct an n-ary search tree with this node layout, simply by building the tree from bottom to top. However, the insert/delete procedure of B-tree and B+-tree is specifically designed for a node with K keys and K+1 pointers.

I don't know how to do insert/updates in a consistent manner when there is no left-most pointer in the nodes; in a way that the theoretical O(log_n) guarantee is still preserved.

Any suggestions? I specifically wonder if such a data structure is known or discussed somewhere.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.