Business Process Reengineering
- PDF / 2,055,850 Bytes
- 104 Pages / 547.087 x 737.008 pts Page_size
- 88 Downloads / 353 Views
Synonyms B-tree
Definition The B+-tree is a disk-based, paginated, dynamically updateable, balanced, and tree-like index structure. It supports the exact match query as well as insertion/ deletion operations in O(logpn) I/Os, where n is the number of records in the tree and p is the page capacity in number of records. It also supports the range searches in O(logpn + t ∕p) I/Os, where t is the number of records in the query result.
Historical Background The binary search tree is a well-known data structure. When the data volume is so large that the tree does not fit in main memory, a disk-based search tree is necessary. The most commonly used disk-based search trees are the B-tree and its variations. Originally invented by Bayer and McCreight [2], the B-tree may be regarded as an extension of the balanced binary tree, since a B-tree is always balanced (i.e., all leaf nodes are on the same level). Since each disk access retrieves or updates an entire block of information between memory and disk rather than a few bytes, a node of the B-tree is expanded to hold more than two child pointers, up to the block capacity. To guarantee worst-case performance, the B-tree requires that every node (except the root) has to be at least half full. Because of this requirement, an exact match query, insertion or deletion operation must access at most O(logpn) nodes, where p is the page capacity in number of child pointers, and n is the number of objects. The most popular variation of #
2009 Springer ScienceþBusiness Media, LLC
the B-tree is the B+-tree [3,4]. In a B+-tree, objects are stored only at the leaf level, and the leaf nodes are organized into a double linked list. As such, the B+tree can be seen as an extension of the Indexed Sequential Access Method (ISAM), a static (and thus possibly unbalanced if updates take place) disk-based search tree proposed by IBM in the mid 1960’s.
Foundations Structure
The B+-tree is a tree structure where every node corresponds to a disk block and which satisfies the following properties: The tree is balanced, i.e., every leaf node has the same depth. An internal node stores a list of keys and a list of pointers. The number of pointers is one more than the number of keys. Every node corresponds to a key range. The key range of an internal node with k keys is partitioned into k+1 sub-ranges, one for each child node. For instance, suppose that the root node has exactly two keys, 100 and 200. The key range of the root node is divided into three subranges (1, 100), (100, 200) and (200, +1). Note that a key in an internal node does not need to occur as the key of any leaf record. Such a key serves only as a means of defining a sub-range. A leaf node stores a list of records, each having a key and some value. Every node except the root node is at least half full. For example suppose that an internal node can hold up to p child pointers (and p-1 keys, of course) and a leaf node can hold up to r records. The half full requirement says any internal node (except the root) must contain at l
Data Loading...
