B+Trees
From
(Difference between revisions)
m (Protected "B+Trees" ([edit=autoconfirmed] (indefinite) [move=autoconfirmed] (indefinite))) |
|||
| Line 3: | Line 3: | ||
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. | 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. | ||
<br/><br/> | <br/><br/> | ||
| + | ---- | ||
| + | {{CS2/ChapNav}} | ||
| + | ---- | ||
| + | [[Category:CS2|{{SUBPAGENAME}}]] | ||
Revision as of 17:08, 9 April 2009
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
