In computer science, a B+ tree is a type of tree which represents sorted data in a way that allows for efficient insertion, retrieval and removal of records, each of which is identified by a key. It is a dynamic, multilevel index, with maximum and minimum bounds on the number of keys in each index segment (usually called a "block" or "node"). In a B+ tree, in contrast to a B-tree, all records are stored at the leaf level of the tree; only keys are stored in interior nodes.
The primary value of a B+ tree is in storing data for efficient retrieval in a block-oriented storage context—in particular, filesystems. This is primarily because unlike binary search trees, B+ trees have very high fanout (typically on the order of 100 or more), which reduces the number of I/O operations required to find an element in the tree.
The NTFS, ReiserFS, NSS, XFS, JFS, and ReFS filesystems all use this type of tree for metadata indexing. Relational database management systems such as IBM DB2, Informix, Microsoft SQL Server, Oracle 8, Sybase ASE, and SQLite support this type of tree for table indices. Key-value database management systems such as CouchDB, Tokyo Cabinet support this type of tree for data access.
Read more about B+ Tree: Overview, Characteristics, Implementation, History
Famous quotes containing the word tree:
“There is hardly an American male of my generation who has not at one time or another tried to master the victory cry of the great ape as it issued from the androgynous chest of Johnny Weissmuller, to the accompaniment of thousands of arms and legs snapping during attempts to swing from tree to tree in the backyards of the Republic.”
—Gore Vidal (b. 1925)