B-tree

A B-tree node stores multiple ordered keys that divide the ranges represented by its children. Lookup determines the appropriate range before descending. This high branching factor keeps the tree relatively shallow and suits storage where reading one page brings several keys into memory for use in the same traversal step.

References: [1]

Insertions may overflow a node, requiring a split and propagation of separating information upward. Deletions can require redistribution or merging. Occupancy rules depend on the variant. These maintenance operations preserve the balance and capacity properties that keep an unfavorable insertion order from turning the structure into a long chain.

References: [2]

Ordering supports locating a range boundary and continuing through neighboring keys, as well as equality lookup. Database use depends on selectivity, collection size, and the query. Multicolumn indexes also depend on column order. Creating an index therefore provides an access option rather than making every possible condition equally efficient.

References: [1]

B-tree-family variants choose different layouts. B+ trees commonly concentrate records or references at leaves and link leaves in order. Database concurrency, page splitting, and recovery mechanisms add further implementation choices. Understanding a particular index therefore requires its variant and storage design as well as the general balanced-tree idea.

References: [2]