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.


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.