Btræstruktur

Btræstruktur, commonly known as the B-tree, is a self-balancing multiway search tree designed to store sorted data and support efficient lookup, insertion, and deletion. It is optimized for storage systems where data is read and written in blocks, such as databases and filesystems.

Structure: A B-tree of minimum degree t has the following constraints: every node contains between t-1 and 2t-1 keys and between t and 2t children; the root has at least one key unless it is a leaf; all leaves appear at the same depth. The keys within a node separate its children into ranges, so that all keys in the left subtrees are less than the corresponding keys in the node, and so on. This organization ensures that a single node access retrieves a large portion of relevant keys.

Operations: Search proceeds from the root to a leaf by comparing the target key with the keys in each node and following the appropriate child pointer. Inserts and deletes are performed with splitting or merging of nodes to preserve the minimum and maximum keys per node, maintaining balance. The height of a B-tree grows slowly with the number of records, yielding logarithmic time for operations. Because nodes align well with disk blocks, B-trees minimize input/output operations for large data sets.

Variants and usage: A related variant is the B+ tree, in which all data records reside in the leaves and internal nodes store only keys for navigation; leaves are linked to support efficient range queries. B-trees and B+ trees are widely used for database indexes and in many filesystems.

History: The B-tree was introduced in 1972 by Rudolf Bayer and Edward McCreight. It remains a foundational structure for persistent storage indexes.