B-Tree

A B-Tree is a self-balancing version of a standardbinary search tree. As a data structure, it is abstract and non-linear. The order of a B-tree defines the maximum number of child nodes a node can have.

%%🖋 Edit in Excalidraw, and the light exported image%%

Properties §

For a B-Tree of order $n$

• Every node has at most $n$ children.

• Every node, except for the root and the leaves, has at least $\lceil n/2\rceil$ children (i.e. $n/2$ rounded up)

• The root node has at least two children (unless it is the only node)

• All leaves appear on the same level.

• A non-leaf node with $k$ children contains $k-1$ keys.

• A B-Tree is still a type of search tree, so it has some properties enforced on child nodes:

• #todo

Resources §

• https://www.youtube.com/watch?v=aZjYr87r1b8