B+ tree
A B+ tree can be viewed as a B-tree in which each node contains only keys (not key–value pairs), and to which an additional level is added at the bottom with linked leaves.
The primary value of a B+ tree is in storing data for efficient retrieval in a block-oriented storage context — in particular, filesystems.
Instead, the notion of maintaining all data in leaf nodes is repeatedly brought up as an interesting variant of the B-tree, which was introduced by R. Bayer and E.
[2] Douglas Comer notes in an early survey of B-trees (which also covers B+ trees) that the B+ tree was used in IBM's VSAM data access software, and refers to an IBM published article from 1973.
[6] This enables each leaf node to keep all of its keys sorted at all times, which then enables each internal node to construct an ordered collection of intervals representing the contiguous extent of values contained in a given leaf.
For this recursive interval information to be retained, internal nodes must additionally contain
representing the least element within the interval covered by the child with index i (which may itself be an internal node, or a leaf).
[1] Given a collection of data records, we want to create a B+ tree index on some key field.
Note : The purpose of the delete algorithm is to remove the desired entry node from the tree structure.
For each function call, we traverse along, using the index to navigate until we find the node, remove it, and then work back up to the root.
[10] The leaves (the bottom-most index blocks) of the B+ tree are often linked to one another in a linked list; this makes range queries or an (ordered) iteration through the blocks simpler and more efficient (though the aforementioned upper bound can be achieved even without this addition).
A B+tree is thus particularly useful as a database system index, where the data typically resides on disk, as it allows the B+tree to actually provide an efficient structure for housing the data itself (this is described in[11]: 238 as index structure "Alternative 1").
For internal blocks, space saving can be achieved by either compressing keys or pointers.
One technique to overcome this problem is to divide each block into sub-blocks and compress them separately.
In this case searching or inserting an element will only need to decompress or compress a sub-block instead of a full block.
[12] APFS uses B+ trees to store mappings from filesystem object IDs to their locations on disk, and to store filesystem records (including directories), though these trees' leaf nodes lack sibling pointers.
[13] Relational database management systems such as IBM Db2,[11] Informix,[11] Microsoft SQL Server,[11] Oracle 8,[11] Sybase ASE,[11] and SQLite[14] support this type of tree for table indices, though each such system implements the basic B+ tree structure with variations and extensions.
Many NoSQL database management systems such as CouchDB[15] and Tokyo Cabinet[16] also support this type of tree for data access and storage.
[citation needed] In such situations, finding the closest neighbor using a B+ tree is productive.
[17] B+ tree is efficiently used to construct an indexed search method called iDistance.
iDistance searches for k nearest neighbors (kNN) in high-dimension metric spaces.
From here, those points can be efficiently implemented using B+ tree, thus, the queries are mapped to single dimensions ranged search.
Moreover, with advanced strategies on frequencies of some highly used leaf or reference point, the B+ tree shows significant results in increasing the endurance of database systems.
