📄 b+trees.mht
字号:
From: <由 Microsoft Internet Explorer 5 保存>
Subject: B+ Trees
Date: Wed, 19 Sep 2001 10:41:24 +0800
MIME-Version: 1.0
Content-Type: multipart/related;
boundary="----=_NextPart_000_0000_01C140F7.A0D64020";
type="text/html"
X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4522.1200
This is a multi-part message in MIME format.
------=_NextPart_000_0000_01C140F7.A0D64020
Content-Type: text/html;
charset="gb2312"
Content-Transfer-Encoding: quoted-printable
Content-Location: http://www.iwu.edu/~sander/C314-Lectures/physicalDB/btree.html
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>B+ Trees</TITLE>
<META content=3D"text/html; charset=3Dgb2312" http-equiv=3DContent-Type>
<META content=3D"MSHTML 5.00.3315.2870" name=3DGENERATOR></HEAD>
<BODY bgColor=3Dwhite>Copyright, 1998, Susan Anderson-Freed <BR>
<HR>
<BR><B>B+ TREES</B> <BR><BR>B+ trees are related to two data structures: =
ISAM=20
Trees and B-Trees. <BR><BR><B>ISAM</B>. As indicated previously, ISAM =
stands for=20
indexed sequential access method. As the name implies, the data is =
maintained in=20
sorted order. A set of index pages provides fast access to the data =
pages. ISAM=20
is a relatively static approach. Although it can accomodate additions =
and=20
deletions, the index pages do not change. Additions are handled through =
overflow=20
pages. Thus, the efficiency of this access method can degrade if there =
is a lot=20
of data movement. <BR><BR><B>B Trees</B>. B Trees are multi-way trees. =
That is=20
each node contains a set of keys and pointers. A B Tree with four keys =
and five=20
pointers represents the minimum size of a B Tree node. A B Tree contains =
only=20
data pages.=20
<P>B Trees are dynamic. That is, the height of the tree grows and =
contracts as=20
records are added and deleted. <BR><BR><B>B+ Trees</B> A B+ Tree =
combines=20
features of ISAM and B Trees. It contains index pages and data pages. =
The data=20
pages always appear as leaf nodes in the tree. The root node and =
intermediate=20
nodes are always index pages. These features are similar to ISAM. Unlike =
ISAM,=20
overflow pages are not used in B+ trees.=20
<P>The index pages in a B+ tree are constructed through the process of =
inserting=20
and deleting records. Thus, B+ trees grow and contract like their B Tree =
counterparts. The contents and the number of index pages reflects this =
growth=20
and shrinkage. <BR><BR>B+ Trees and B Trees use a "fill factor" to =
control the=20
growth and the shrinkage. A 50% fill factor would be the minimum for any =
B+ or B=20
tree. As our example we use the smallest page structure. This means that =
our B+=20
tree conforms to the following guidelines. <BR><BR>
<CENTER>
<TABLE border=3D1 cellPadding=3D5>
<TBODY>
<TR>
<TD>Number of Keys/page
<TD>4</TD>
<TR>
<TD>Number of Pointers/page</TD>
<TD>5=20
<TR>
<TD>Fill Factor</TD>
<TD>50%</TD>
<TR>
<TD>Minimum Keys in each page</TD>
<TD>2 </TR></TBODY></TABLE></CENTER><BR><BR>As this table indicates =
each page=20
must have a minimum of two keys. The root page may violate this rule.=20
<P>The following table shows a B+ tree. As the example illustrates this =
tree=20
does not have a full index page. (We have room for one more key and =
pointer in=20
the root page.) In addition, one of the data pages contains empty slots. =
<BR><BR>
<CENTER>
<TABLE border=3D1 cellPadding=3D5>
<CAPTION>B+ Tree with four keys</CAPTION>
<TBODY>
<TR>
<TD><IMG border=3D0=20
=
src=3D"http://www.iwu.edu/~sander/C314-Lectures/physicalDB/btree3.jpeg"> =
</TD></TR></TBODY></TABLE></CENTER><BR><BR><B>Adding Records to a B+ =
Tree</B>=20
<BR><BR>The key value determines a record's placement in a B+ tree. The =
leaf=20
pages are maintained in sequential order AND a doubly linked list (not =
shown)=20
connects each leaf page with its sibling page(s). This doubly linked =
list speeds=20
data movement as the pages grow and contract.=20
<P>We must consider three scenarios when we add a record to a B+ tree. =
Each=20
scenario causes a different action in the insert algorithm. The =
scenarios are:=20
<BR><BR>
<CENTER>
<TABLE border=3D1 cellPadding=3D5>
<CAPTION>The <TT>insert</TT> algorithm for B+ Trees</CAPTION>
<TBODY>
<TR>
<TH>Leaf Page Full</TH>
<TH>Index Page FULL</TH>
<TH>Action</TH></TR>
<TR>
<TD>NO </TD>
<TD>NO</TD>
<TD>Place the record in sorted position in the appropriate leaf =
page</TD></TR>
<TR>
<TD>YES</TD>
<TD>NO</TD>
<TD>
<OL>
<LI>Split the leaf page=20
<LI>Place Middle Key in the index page in sorted order.=20
<LI>Left leaf page contains records with keys below the middle =
key.=20
<LI>Right leaf page contains records with keys equal to or =
greater than=20
the middle key. </LI></OL></TD>
<TR>
<TD>YES</TD>
<TD>YES</TD>
<TD>
<OL>
<LI>Split the leaf page.=20
<LI>Records with keys < middle key go to the left leaf page.=20
<LI>Records with keys >=3D middle key go to the right leaf =
page.=20
<BR><BR>
<LI>Split the index page.=20
<LI>Keys < middle key go to the left index page.=20
<LI>Keys > middle key go to the right index page.=20
<LI>The middle key goes to the next (higher level) index. =
<BR><BR>IF the=20
next level index page is full, continue splitting the index =
pages.=20
=
</LI></OL></TD></TR></TBODY></TABLE></CENTER><BR><BR><B>Illustrations of =
the=20
<B>insert</B> algorithm</B> <BR><BR>The following examples illlustrate =
each of=20
the <B>insert</B> scenarios. We begin with the simplest scenario: =
inserting a=20
record into a leaf page that is not full. Since only the leaf node =
containing 25=20
and 30 contains expansion room, we're going to insert a record with a =
key value=20
of 28 into the B+ tree. The following figures shows the result of this =
addition.=20
<BR><BR>
<CENTER>
<TABLE border=3D1 cellPadding=3D5>
<CAPTION>Add Record with Key 28 </CAPTION>
<TBODY>
<TR>
<TD><IMG border=3D0=20
=
src=3D"http://www.iwu.edu/~sander/C314-Lectures/physicalDB/btree4.jpeg"> =
</TD></TR></TBODY></TABLE></CENTER><BR><BR><B>Adding a record when the =
leaf page=20
is full but the index page is not</B> <BR><BR>Next, we're going to =
insert a=20
record with a key value of 70 into our B+ tree. This record should go in =
the=20
leaf page containing 50, 55, 60, and 65. Unfortunately this page is =
full. This=20
means that we must split the page as follows: <BR><BR>
<CENTER>
<TABLE border=3D1 cellPadding=3D5>
<TBODY>
<TR>
<TH>Left Leaf Page</TH>
<TH>Right Leaf Page</TH></TR>
<TR>
<TD><TT>50 55 </TT></TD>
<TD><TT>60 65 70</TT></TD></TR></TBODY></TABLE></CENTER><BR><BR>The =
middle key=20
of 60 is placed in the index page between 50 and 75.=20
<P>The following table shows the B+ tree after the addition of 70. =
<BR><BR>
<CENTER>
<TABLE border=3D1 cellPadding=3D5>
<CAPTION>Add Record with Key 70 </CAPTION>
<TBODY>
<TR>
<TD><IMG border=3D0=20
=
src=3D"http://www.iwu.edu/~sander/C314-Lectures/physicalDB/btree5.jpeg"> =
</TD></TR></TBODY></TABLE></CENTER><BR><BR><B>Adding a record when =
both the leaf=20
page and the index page are full</B>=20
<P>As our last example, we're going to add a record containing a key =
value of 95=20
to our B+ tree. This record belongs in the page containing 75, 80, 85, =
and 90.=20
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -