s_btr.htm
来自「Data Structure Ebook」· HTM 代码 · 共 188 行
HTM
188 行
<html>
<head>
<title>B-Trees</title>
</head>
<body bgcolor="#ffffff">
<p align=right>
<a href="s_man.htm" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_man.htm" target="_top"><img src="c_man.gif" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/niemann/c_man.gif" width=74 height=19 border=0></A>
</p>
<h1>B-Trees</h1>
Dictionaries for very large files typically reside on secondary storage,
such as a disk. The dictionary is implemented as an index to the
actual file and contains the key and record address of data. To implement
a dictionary we could use
<a href="s_rbt.htm" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_rbt.htm">red-black trees</a>,
replacing pointers with
offsets from the beginning of the index file, and use random access
to reference nodes of the tree. However, every transition on a link
would imply a disk access, and would be prohibitively expensive.
Recall that low-level disk I/O accesses disk by sectors (typically 256 bytes).
We could equate node size to sector size, and
group several keys together in each node to
minimize the number of I/O operations. This is the principle behind B-trees.
Good references for B-trees include
<a href="javascript:if(confirm('http://www.amazon.com/exec/obidos/ISBN=0201896850/none01A/ \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://www.amazon.com/exec/obidos/ISBN=0201896850/none01A/'" tppabs="http://www.amazon.com/exec/obidos/ISBN=0201896850/none01A/" target="_top">Knuth [1998]</a> and
<a href="javascript:if(confirm('http://www.amazon.com/exec/obidos/ISBN=0262031418/none01A/ \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://www.amazon.com/exec/obidos/ISBN=0262031418/none01A/'" tppabs="http://www.amazon.com/exec/obidos/ISBN=0262031418/none01A/" target="_top">Cormen [1990]</a>.
For B<sup>+</sup>-trees, consult
<a href="javascript:if(confirm('http://www.amazon.com/exec/obidos/ISBN=0201000237/none01A/ \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://www.amazon.com/exec/obidos/ISBN=0201000237/none01A/'" tppabs="http://www.amazon.com/exec/obidos/ISBN=0201000237/none01A/" target="_top">Aho [1983]</a>.
<h2>Theory</h2>
Figure 4-3
illustrates a B-tree with 3 keys/node.
Keys in internal nodes are surrounded by pointers, or record offsets,
to keys that are less than or greater than, the key value. For example,
all keys less than 22 are to the left and all keys greater than 22 are
to the right. For simplicity, I have not shown the record address
associated with each key.
<p>
<center>
<h3><a name="Fig4-3">
<img src="s_fig43.gif" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_fig43.gif" vspace=5 width=509 height=176><br>
Figure 4-3: B-Tree</a>
</h3>
</center>
<p>
We can locate any key in this 2-level tree with three disk accesses.
If we were to group 100 keys/node, we could search over 1,000,000 keys
in only three reads. To ensure this property holds, we must maintain a
balanced tree during insertion and deletion. During insertion, we examine
the child node to verify that it is able to hold an additional node.
If not, then a new sibling node is added to the tree, and the child's
keys are redistributed to make room for the new node. When descending
for insertion and the root is full, then the root is spilled to new
children, and the level of the tree increases. A similar action is taken
on deletion, where child nodes may be absorbed by the root.
This technique for altering the height of the tree maintains a balanced tree.
<center>
<p><a name="Tbl4-1"></a>
<table border cellspacing=0 cellpadding=3>
<caption align=bottom><h3>Table 4-1: B-Tree Implementations</h3></caption>
<tr><th></th><th>B-Tree</th><th>B*-Tree</th><th>B<sup>+</sup>-Tree</th><th>B<sup>++</sup>-Tree</th></tr>
<tr align=left>
<td>data stored in</td>
<td>any node</td>
<td>any node</td>
<td>leaf only</td>
<td>leaf only</td>
<tr align=left>
<td>on insert, split</td>
<td>1 x 1 –>2 x 1/2</td>
<td>2 x 1 –>3 x 2/3</td>
<td>1 x 1 –>2 x 1/2</td>
<td>3 x 1 –>4 x 3/4</td>
<tr align=left>
<td>on delete, join</td>
<td>2 x 1/2 –>1 x 1</td>
<td>3 x 2/3 –>2 x 1</td>
<td>2 x 1/2 –>1 x 1</td>
<td>3 x 1/2 –>2 x 3/4</td>
</table>
</center>
<p>
Several variants on the B-tree are listed in
Table 4-1.
The <em>standard</em>
B-tree stores keys and data in both internal and leaf nodes.
When descending the tree during insertion, a full child node is
first redistributed to adjacent nodes. If the adjacent nodes are
also full, then a new node is created, and half the keys in the child
are moved to the newly created node.
During deletion, children that are 1/2 full first attempt to obtain
keys from adjacent nodes. If the adjacent nodes are also 1/2 full, then
two nodes are joined to form one full node.
B*-trees are similar, only the nodes are kept 2/3 full. This results
in better utilization of space in the tree, and slightly better performance.
<p>
<center>
<h3><a name="Fig4-4">
<img src="s_fig44.gif" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_fig44.gif" vspace=5 width=505 height=176><br>
Figure 4-4: B<sup>+</sup>-Tree</a>
</h3>
</center>
<p>
Figure 4-4
illustrates a B<sup>+</sup>-tree. <em>All</em> keys are stored at
the leaf level,
with their associated data values. Duplicates of the keys appear in internal
parent nodes to guide the search. Pointers have a slightly different meaning
than in conventional B-trees. The left pointer designates all keys less than
the value, while the right pointer designates all keys
<em>greater than or equal to</em> (GE) the value.
For example, all keys less than 22 are on the left
pointer, and all keys greater than or equal to 22 are on the right.
Notice that key 22 is duplicated in the leaf, where the associated data
may be found. During insertion and deletion, care must be taken to properly
update parent nodes. When modifying the first key in a leaf, the tree is
walked from leaf to root. The last GE pointer found while descending
the tree will require
modification to reflect the new key value. Since all keys are in the
leaf nodes, we may link them for sequential access.
<p>
The last method, B<sup>++</sup>-trees, is something of my own invention.
The organization is similar to B<sup>+</sup>-trees, except for the
split/join strategy.
Assume each node can hold <i>k</i> keys, and the root node
holds 3<i>k</i> keys.
Before we descend to a child node during insertion,
we check to see if it is full.
If it is, the keys in the child node and two nodes adjacent to the child are
all merged and redistributed.
If the two adjacent nodes are also full,
then another node is added, resulting in four nodes, each 3/4 full.
Before we descend to a child node during deletion,
we check to see if it is 1/2 full.
If it is, the keys in the child node and two nodes adjacent to the child are
all merged and redistributed.
If the two adjacent nodes are also 1/2 full,
then they are merged into two nodes, each 3/4 full.
This is halfway between 1/2 full and completely full, allowing for an equal number of insertions or deletions in the future.
<p>
Recall that the root node holds 3<i>k</i> keys.
If the root is full during insertion, we distribute the keys to four new nodes,
each 3/4 full.
This increases the height of the tree.
During deletion, we inspect the child nodes. If there are only three child
nodes, and they are all 1/2 full, they are gathered into the root,
and the height of the tree decreases.
<p>
Another way of expressing
the operation is to say we are <em>gathering</em> three nodes,
and then <em>scattering</em>
them. In the case of insertion, where we need an extra node,
we scatter to four nodes. For deletion, where a node must be deleted,
we scatter to two nodes. The symmetry of the operation allows the
gather/scatter routines to be shared by insertion and deletion in
the implementation.
<h2>Implementation</h2>
An
<a href="javascript:if(confirm('http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_btr.txt \n\nThis file was not retrieved by Teleport Pro, because it is linked too far away from its Starting Address. If you increase the in-domain depth setting for the Starting Address, this file will be queued for retrieval. \n\nDo you want to open it from the server?'))window.location='http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_btr.txt'" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_btr.txt">ANSI-C implementation</a>
of a B<sup>++</sup>-tree is included.
In the implementation-dependent section, you'll need to define
<b>bAdrType</b> and <b>eAdrType</b>, the types associated with
B-tree file offsets and data file offsets, respectively. You'll
also need to provide a callback function which is used by the
B<sup>++</sup>-tree algorithm to compare keys. Functions are provided to
insert/delete keys, find keys, and access keys sequentially.
Function <b>main</b>, at the bottom of the file, provides a simple
illustration for insertion.
<p>
The code provided allows for multiple indices to the same data.
This was implemented by returning a <em>handle</em> when the index is opened.
Subsequent accesses are done using the supplied handle.
Duplicate keys are allowed. Within one index, all keys must be the
same length. A binary search was implemented to search each node.
A flexible buffering scheme allows nodes to be retained in memory until
the space is needed. If you expect access to be somewhat ordered,
increasing the <b>bufCt</b> will reduce paging.
</body>
</html>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?