CODEWITHSUNDEEP
data-structures
overclockwise
overclockwise

Reputation: 65

B(+)Tree internal structure

I have a rough understanding of the overall high-level workings of b-trees, but something that people always seem to gloss over is the inner workings of each node.

My current understanding is that each node consists of an array of keys and an array of pointers (pointing either to another node or to the relevant data). But how do you perform insertions on a sorted array efficiently. Wouldn't it be O(n) (n as the size of the array, not the elements in the whole tree) to shuffle elements up or down every time you insert/delete a key?

Upvotes: 1

Views: 107

Answers (1)

user555045
user555045

Reputation: 64904

The familiar "it takes O(n) to insert into a sorted array" comes from the case where n refers to the size of the array.

In a B(+/*/you name it) tree, the nodes are arrays of constant size, namely the branching factor. (a node may also be partially filled, but that doesn't change anything here)

And if your array is only O(1) long, it's hard to get a factor of n out of thin air, so inserting into it (and various other operations) are O(1).

Upvotes: 1

Related Questions