B+Trees

From

Revision as of 10:12, 13 May 2009 by Mitchfry (Talk | contribs)
(diff) ← Older revision | Current revision (diff) | Newer revision → (diff)
Jump to: navigation, search
← B-Trees ↑ Multi-Way_Trees End


The variation of a B-Tree that is most often implemented in the B+ Tree. In this tree, internal nodes store only keys and all the data is stored in the leaves. The keys are simply “sign posts” to direct a search to the proper leaf. In addition, nodes have sibling pointers, so that the nodes at each level form a linked list.

While B-Trees have many uses, a common use is to implement the directory structure of an operating system’s file system using B-Trees. The key idea is that one node of the tree is the same size as a disk block.


CS2: Data Structures
Theory of Computation - ADT Preliminaries
Linear ADTs - Tree ADTs - Graph ADTs - Unordered Collection ADTs


Personal tools
MediaWiki Appliance - Powered by TurnKey Linux