B*-tree

B*-tree

A B*-tree is a tree data structure, a variety of B-tree used in the HFS and Reiser4 file systems, which requires non-root nodes to be at least 2/3 full instead of 1/2. To maintain this, instead of immediately splitting up a node when it gets full, its keys are shared with the node next to it. When both are full, then the two of them are split into three. It also requires the 'leftmost' key never to be used. The term is not in general use today as the implementation was never looked on positively by the computer science community-at-large; most people use "B-tree" generically to refer to all the variations and refinements of the basic data structure.

A B*-tree should not be confused with a B+ tree, which is one where the leaf nodes of the tree are chained together in the form of a linked list. That is efficient for searching at the cost of a more expensive insertion.

There is also a B**-tree defined by an academic professor listed in the IEEE 0-8186-4212-2 1993. [cite conference |author=Anestis A. Toptsis |date=1993-05-27 |title=B**-tree: a data organization method for high storage utilization |booktitle=Computing and Information, 1993. Proceedings ICCI '93. |pages=pages 277–281 |location=Sudbury, Ontaro, Canada |id=ISBN 0-8186-4212-2 |url=http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=315364 |accessdate=2007-02-17 ]

References

External links

* [http://www.nist.gov/dads/HTML/bstartree.html Dictionary of Algorithms and Data Structures entry for B*-tree]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Tree — /tree/, n. Sir Herbert Beerbohm /bear bohm/, (Herbert Beerbohm), 1853 1917, English actor and theater manager; brother of Max Beerbohm. * * * I Woody perennial plant. Most trees have a single self supporting trunk containing woody tissues, and in …   Universalium

  • Tree — (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree, oak, do ry… …   The Collaborative International Dictionary of English

  • Tree bear — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

  • Tree beetle — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

  • Tree bug — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

  • Tree cat — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

  • Tree clover — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

  • Tree crab — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

  • Tree creeper — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

  • Tree cricket — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

  • Tree crow — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”