B+-Tree — Basic Information
An M-ary tree (M>3)
Leaves contain data items
all are at the same depth
each node has L/2 to L data (usually L << M in practice)
Internal nodes contain searching keys
each node has M/2 to M children
each node has (M/2)-1 to (M-1) searching keys
key i is the smallest key in subtree i+1
Root
can be a single leaf, or has 2 to M children
