📄 chap19.htm
字号:
<HTML><HEAD>
<TITLE>Intro to Algorithms: CHAPTER 19: B-TREES</TITLE></HEAD><BODY BGCOLOR="#FFFFFF">
<a href="chap20.htm"><img align=right src="../../images/next.gif" alt="Next Chapter" border=0></A>
<a href="toc.htm"><img align=right src="../../images/toc.gif" alt="Return to Table of Contents" border=0></A>
<a href="partv.htm"><img align=right src="../../images/prev.gif" alt="Previous Chapter" border=0></A>
<h1><a name="0853_1617">CHAPTER 19: B-TREES<a name="0853_1617"></h1><P>
<a name="0853_160b"><a name="0853_160c"><a name="0853_160d"><a name="0853_160e"><a name="0853_160f"><a name="0853_1610">B-trees are balanced search trees designed to work well on magnetic disks or other direct-access secondary storage devices. B-trees are similar to red-black trees (Chapter 14), but they are better at minimizing disk I/O operations.<P>
B-trees differ significantly from red-black trees in that B-tree nodes may have many children, from a handful to thousands. That is, the "branching factor" of a B-tree can be quite large, although it is usually determined by characteristics of the disk unit used. B-trees are similar to red-black trees in that every <I>n</I>-node B-tree has height <I>O</I>(lg <I>n</I>), although the height of a B-tree can be considerably less than that of a red-black tree because its branching factor can be much larger. Therefore, B-trees can also be used to implement many dynamic-set operations in time <I>O</I>(lg <I>n</I>).<P>
B-trees generalize binary search trees in a natural manner. Figure 19.1 shows a simple B-tree. If a B-tree node <I>x</I> contains <I>n</I>[<I>x</I>] keys, then <I>x </I>has <I>n</I>[<I>x</I>] + 1 children. The keys in node <I>x</I> are used as dividing points separating the range of keys handled by <I>x</I> into <I>n</I>[<I>x</I>] + 1 subranges, each handled by one child of <I>x</I>. When searching for a key in a B-tree, we make an (<I>n</I>[<I>x</I>] + 1)-way decision based on comparisons with the <I>n</I>[<I>x</I>] keys stored at node <I>x</I>.<P>
<img src="381_a.gif"><P>
<h4><a name="0853_1618">Figure 19.1 A B-tree whose keys are the consonants of English. An internal node x containing n[x] keys has n[x] + 1 children. All leaves are at the same depth in the tree. The lightly shaded nodes are examined in a search for the letter R.<a name="0853_1618"></sub></sup></h4><P>
<img src="382_a.gif"><P>
<h4><a name="0853_1619">Figure 19.2 A typical disk drive.<a name="0853_1619"></sub></sup></h4><P>
Section 19.1 gives a precise definition of B-trees and proves that the height of a B-tree grows only logarithmically with the number of nodes it contains. Section 19.2 describes how to search for a key and insert a key into a B-tree, and Section 19.3 discusses deletion. Before proceeding, however, we need to ask why data structures designed to work on a magnetic disk are evaluated differently than data structures designed to work in main random-access memory.<P>
Data structures on secondary storage<P>
<a name="0853_1611"><a name="0853_1612">There are many different technologies available for providing memory capacity in a computer system. The <I><B>primary memory</I></B> (or <I><B>main memory</I></B>) of a computer system typically consists of silicon memory chips, each of which can hold 1 million bits of data. This technology is more expensive per bit stored than magnetic storage technology, such as tapes or disks. A typical computer system has <I><B>secondary storage</I></B> based on magnetic disks; the amount of such secondary storage often exceeds the amount of primary memory by several orders of magnitude.<P>
<a name="0853_1613">Figure 19.2 shows a typical disk drive. The disk surface is covered with a magnetizable material. The read/write head can read or write data magnetically on the rotating disk surface. The read/write arm can position the head at different distances from the center of the disk. When the head is stationary, the surface that passes underneath it is called a <I><B>track</I>.</B> Theinformation stored on each track is often divided into a fixed number of equal-sized <I><B>pages</I></B>; for a typical disk, a page might be 2048 bytes in length.The basic unit of information storage and retrieval is usually a page of information--that is, disk reads and writes are typically of entire pages.The <I><B>access time</I></B>--the time required to position the read/write head and to wait for a given page of information to pass underneath the head--may be large (e.g., 20 milliseconds), while the time to read or write a page, once accessed, is small. The price paid for the low cost of magnetic storage techniques is thus the relatively long time it takes to access the data. Since moving electrons is much easier than moving large (or even small) objects, storage devices that are entirely electronic, such as silicon memory chips, have a much smaller access time than storage devices that have moving parts, such as magnetic disk drives. However, once everything is positioned correctly, reading or writing a magnetic disk is entirely electronic (aside from the rotation of the disk), and large amounts of data can be read or written quickly.<P>
Often, it takes more time to access a page of information and read it from a disk than it takes for the computer to examine all the information read. For this reason, in this chapter we shall look separately at the two principal components of the running time:<P>
<FONT FACE="Courier New" SIZE=2><img src="../images/dot12.gif"></FONT> the number of disk accesses, and<P>
<a name="0853_1614"><FONT FACE="Courier New" SIZE=2><img src="../images/dot12.gif"></FONT> the CPU (computing) time.<P>
The number of disk accesses is measured in terms of the number of pages of information that need to be read from or written to the disk. We note that disk access time is not constant--it depends on the distance between the current track and the desired track and also on the initial rotational state of the disk. We shall nonetheless use the number of pages read or written as a crude first-order approximation of the total time spent accessing the disk.<P>
In a typical B-tree application, the amount of data handled is so large that all the data do not fit into main memory at once. The B-tree algorithms copy selected pages from disk into main memory as needed and write back onto disk pages that have changed. Since the B-tree algorithms only need a constant number of pages in main memory at any time, the size of main memory does not limit the size of B-trees that can be handled.<P>
<a name="0853_1615"><a name="0853_1616">We model disk operations in our pseudocode as follows. Let <I>x</I> be a pointer to an object. If the object is currently in the computer's main memory, then we can refer to the fields of the object as usual: <I>key</I>[<I>x</I>], for example. If the object referred to by <I>x</I> resides on disk, however, then we must perform the operation <FONT FACE="Courier New" SIZE=2>DISK</FONT>-<FONT FACE="Courier New" SIZE=2>READ</FONT>(<I>x</I>) to read object <I>x</I> into main memory before its fields can be referred to. (We assume that if <I>x</I> is already in main memory, then <FONT FACE="Courier New" SIZE=2>DISK</FONT>-<FONT FACE="Courier New" SIZE=2>READ</FONT>(<I>x</I>) requires no disk accesses; it is a "noop.") Similarly, the operation <FONT FACE="Courier New" SIZE=2>DISK</FONT>-<FONT FACE="Courier New" SIZE=2>WRITE</FONT>(<I>x</I>) is used to save any changes that have been made to the fields of object <I>x</I>. That is, the typical pattern for working with an object is as follows.<P>
<pre>1 . . .</sub></sup></pre><P>
<pre>2<I> x</I> <img src="../images/arrlt12.gif"> a pointer to some object</sub></sup></pre><P>
<pre>3 DISK-READ(<I>x</I>)</sub></sup></pre><P>
<pre>4 operations that access and/or modify the fields of <I>x</I></sub></sup></pre><P>
<pre>5 DISK-WRITE(<I>x</I>) <img src="383_a.gif"> Omitted if no fields of <I>x</I> were changed.</sub></sup></pre><P>
<pre>6 other operations that access but do not modify fields of <I>x</I></sub></sup></pre><P>
<pre>7 ...</sub></sup></pre><P>
<img src="384_a.gif"><P>
<h4><a name="0853_161a">Figure 19.3 A B-tree of height 2 containing over one billion keys. Each internal node and leaf contains 1000 keys. There are 1001 nodes at depth 1 and over one million leaves at depth 2. Shown inside each node x is n[x], the number of keys in x.<a name="0853_161a"></sub></sup></h4><P>
The system can only keep a limited number of pages in main memory at any one time. We shall assume that pages no longer in use are flushed from main memory by the system; our B-tree algorithms will ignore this issue.<P>
Since in most systems the running time of a B-tree algorithm is determined mainly by the number of <FONT FACE="Courier New" SIZE=2>DISK</FONT>-<FONT FACE="Courier New" SIZE=2>READ</FONT> and <FONT FACE="Courier New" SIZE=2>DISK</FONT>-<FONT FACE="Courier New" SIZE=2>WRITE</FONT> operations it performs, it is sensible to use these operations intensively by having them read or write as much information as possible. Thus, a B-tree node is usually as large as a whole disk page. The number of children a B-tree node can have is therefore limited by the size of a disk page.<P>
For a large B-tree stored on a disk, branching factors between 50 and 2000 are often used, depending on the size of a key relative to the size of a page. A large branching factor dramatically reduces both the height of the tree and the number of disk accesses required to find any key. Figure 19.3 shows a B-tree with a branching factor of 1001 and height 2 that can store over one billion keys; nevertheless, since the root node can be kept permanently in main memory, only <I>two</I> disk accesses at most are required to find any key in this tree!<P>
<h1><a name="0855_1621">19.1 Definition of B-trees<a name="0855_1621"></h1><P>
<a name="0855_1617">To keep things simple, we assume, as we have for binary search trees and red-black trees, that any "satellite information" associated with a key is stored in the same node as the key. In practice, one might actually store with each key just a pointer to another disk page containing the satellite information for that key. The pseudocode in this chapter implicitly assumes that the satellite information associated with a key, or the pointer to such satellite information, travels with the key whenever the key is moved from node to node. Another commonly used B-tree organization stores all the satellite information in the leaves and only stores keys and child pointers in the internal nodes, thus maximizing the branching factor of the internal nodes.<P>
A <I><B>B-tree</I></B> <I>T</I> is a rooted tree (with root <I>root</I>[<I>T</I>]) having the following properties.<P>
1. Every node <I>x</I> has the following fields:<P>
a. <I>n</I>[<I>x</I>], the number of keys currently stored in node <I>x</I>,<P>
b. the <I>n</I>[<I>x</I>] keys themselves, stored in nondecreasing order: <I>key</I><SUB>1</SUB>[<I>x</I>] <img src="../images/lteq12.gif"> <I>key<SUB>2</I></SUB>[<I>x</I>] <img src="../images/lteq12.gif"> <img src="../images/dot10.gif"> <img src="../images/dot10.gif"> <img src="../images/dot10.gif"> <img src="../images/lteq12.gif"> <I>key<SUB>n</I>[<I>x</I>]</SUB>[<I>x</I>], and<P>
c. <I>leaf </I>[<I>x</I>], a boolean value that is <FONT FACE="Courier New" SIZE=1>TRUE</FONT> if <I>x</I> is a leaf and <FONT FACE="Courier New" SIZE=1>FALSE</FONT> if <I>x</I> is an internal node.<P>
2. If <I>x</I> is an internal node, it also contains <I>n</I>[<I>x</I>] + 1 pointers <I>c</I><SUB>1</SUB><I> </I>[<I>x</I>]<I>, c<SUB>2</I></SUB>[<I>x</I>], . . . , <I>c<SUB>n</I>[<I>x</I>]<I>+</I>1</SUB>[<I>x</I>] to its children. Leaf nodes have no children, so their <I>c<SUB>i</I></SUB> fields are undefined.<P>
3. The keys <I>key<SUB>i</I></SUB>[<I>x</I>] separate the ranges of keys stored in each subtree: if <I>k<SUB>i</I></SUB> is any key stored in the subtree with root <I>c<SUB>i</I></SUB>[<I>x</I>], then<P>
<pre><I>k</I><SUB>1</SUB> <img src="../images/lteq12.gif"> <I>key</I><SUB>1</SUB>[<I>x</I>] <img src="../images/lteq12.gif"> <I>k</I><SUB>2</SUB> <img src="../images/lteq12.gif"> <I>key</I><SUB>2</SUB>[<I>x</I>] <img src="../images/lteq12.gif"> <img src="../images/dot10.gif"> <img src="../images/dot10.gif"> <img src="../images/dot10.gif"> <img src="../images/lteq12.gif"> key<SUB>n[<I>x</I>]</SUB>[<I>x</I>] <img src="../images/lteq12.gif"> <I>k<SUB>n</I>[<I>x</I>]+1</SUB> .</sub></sup></pre><P>
<I>4. </I>Every leaf has the same depth, which is the tree's height<I> h</I>.<P>
<a name="0855_1618"><a name="0855_1619"><a name="0855_161a"> 5. There are lower and upper bounds on the number of keys a node can contain. These bounds can be expressed in terms of a fixed integer <I>t</I> <img src="../images/gteq.gif"> 2 called the <I><B>minimum degree</I></B> of the B-tree:<P>
a. Every node other than the root must have at least <I>t</I> - 1 keys. Every internal node other than the root thus has at least <I>t</I> children. If the tree is nonempty, the root must have at least one key.<P>
<a name="0855_161b"><a name="0855_161c">b. Every node can contain at most 2<I>t</I> - 1 keys. Therefore, an internal node can have at most 2<I>t</I> children. We say that a node is <I><B>full</I></B> if it contains exactly 2<I>t</I> - 1 keys.<P>
<a name="0855_161d"><a name="0855_161e"><a name="0855_161f"><a name="0855_1620">The simplest B-tree occurs when <I>t</I> = 2. Every internal node then has either 2, 3, or 4 children, and we have a <I><B>2-3-4</I></B> <I><B>tree.</I></B> In practice, however, much larger values of <I>t</I> are typically used.<P>
<h2>The height of a B-tree</h2><P>
<a name="0856_1621"><a name="0856_1622">The number of disk accesses required for most operations on a B-tree is proportional to the height of the B-tree. We now analyze the worst-case height of a B-tree.<P>
<a name="0856_1624">Theorem 19.1<a name="0856_1624"><P>
If <I>n</I> <img src="../images/gteq.gif"> 1, then for any <I>n</I>-key B-tree <I>T</I> of height <I>h</I> and minimum degree <I>t</I> <img src="../images/gteq.gif"> 2,<P>
<img src="385_a.gif"><P>
<img src="386_a.gif"><P>
<h4><a name="0856_1625">Figure 19.4 A B-tree of height 3 containing a minimum possible number of keys. Shown inside each node x is n[x].<a name="0856_1625"></sub></sup></h4><P>
<I><B>Proof</I></B> If a B-tree has height <I>h</I>, the number of its nodes is minimized when the root contains one key and all other nodes contain <I>t</I> - 1 keys. In this case, there are 2 nodes at depth 1, 2<I>t</I> nodes at depth 2, 2<I>t</I><SUP>2</SUP> nodes at depth 3, and so on, until at depth <I>h</I> there are 2<I>t<SUP>h-</I>1 </SUP>nodes. Figure 19.4 illustrates such a tree for <I>h</I> = 3. Thus, the number <I>n</I> of keys satisfies the inequality<P>
<img src="386_b.gif"><P>
which implies the theorem. <P>
<a name="0856_1623">Here we see the power of B-trees, as compared to red-black trees. Although the height of the tree grows as <I>O</I>(lg <I>n</I>) in both cases (recall that <I>t</I> is a constant), for B-trees the base of the logarithm can be many times larger. Thus, B-trees save a factor of about lg <I>t</I> over red-black trees in the number of nodes examined for most tree operations. Since examining an arbitrary node in a tree usually requires a disk access, the number of disk accesses is substantially reduced.<P>
<P>
<h2><a name="0857_1626">Exercises<a name="0857_1626"></h2><P>
<a name="0857_1627">19.1-1<a name="0857_1627"><P>
Why don't we allow a minimum degree of <I>t</I> = 1?<P>
<a name="0857_1628">19.1-2<a name="0857_1628"><P>
For what values of <I>t</I> is the tree of Figure 19.1 a legal B-tree?<P>
<a name="0857_1629">19.1-3<a name="0857_1629"><P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -