B-tree

A height-balanced search-tree data structure that stores multiple keys per node and keeps all leaves at the same depth. Its high branching factor reduces the number of storage accesses needed for search, insertion, and deletion.

B-tree node: A B-tree node contains multiple ordered keys and child pointers, dividing its key range among its subtrees. Its keys and child pointers let one node represent many search decisions.
Search tree: A tree structure whose node ordering lets searches discard subtrees that cannot contain a target key. A B-tree generalizes ordered searching by placing several keys in each node.
Database index: An auxiliary data structure that accelerates retrieval of records by search keys. B-trees support ordered lookups and updates in database indexes.
Binary search tree: A search tree in which each node has at most two children and keys follow an ordering invariant. Its low branching factor usually creates more levels than a B-tree for stored data.
B-tree insertion: The procedure for adding a key to a B-tree while preserving its ordering and balance invariants. Insertion handles full nodes by splitting them and may increase the tree's height.
Multiway tree: A rooted tree in which a node may have more than two children. B-trees use many child branches to reduce the number of levels.
File system: A system for organizing, storing, naming, and retrieving files on storage devices. Some file systems use B-tree variants to index directories and metadata.
AVL tree: A self-balancing binary search tree that maintains a strict height difference bound between child subtrees. AVL trees optimize in-memory comparisons rather than storage-block access.
B-tree deletion: The procedure for removing a key from a B-tree while preserving its ordering and balance invariants. Deletion repairs nodes that fall below their minimum occupancy.
Balanced tree: A tree whose shape is constrained to prevent search paths from becoming excessively long. B-tree balance requires every leaf to lie at the same depth.

Linked from 8 pages