B-trees are a type of self-balancing tree structure designed for storing huge amounts of data for fast query and retrieval. B-trees can have multiple key/value pairs in a node, sorted ascendingly by key order. For a tree to be classified as a B-tree, it must fulfill the following conditions: * the nodes in a B-tree of order m can have a maximum of m children * each internal node (non-leaf and non-root) can have at least (m/2) children (rounded up) * the root should have at least two children – unless it’s a leaf a non-leaf node with k children should have k-1 keys * all leaves must appear on the same level. The most well-known version of the B-tree is the B+tree. What distinguishes the B+tree from the B-tree are two main aspects: * all leaf nodes are linked together in a doubly-linked list * satellite data is stored on the leaf nodes only. Internal nodes only hold keys and act as routers to the correct leaf node. DBMSs leverage the logarithmic efficiency of B-tree indexing to reduce the number of reads required to find a particular record. B-trees are typically constructed so that each node takes up a single page in memory and they are designed to reduce the number of accesses by requiring that each node be at least half full. Finally, although B-trees are useful, B+trees are more popular. In fact, 99% of database management systems use B+trees for indexing. This is because the B+tree holds no data in the internal nodes. This maximizes the number of keys stored in a node thereby minimizing the number of levels needed in a tree. Smaller tree depth invariably means faster search.
Keywords
Subscribe for latest offers & updates
We hate spam too.