b+trees.mht

CMXBTree 的主要作用是在内存中建立一棵B+树

Since this page is full we split it into two pages: <BR><BR>
<CENTER>
<TABLE border=3D1 cellPadding=3D5>
  <TBODY>
  <TR>
    <TH>Left Leaf Page</TH>
    <TH>Right Leaf Page</TH></TR>
  <TR>
    <TD><TT>75 80 </TT></TD>
    <TD><TT>85 90 95</TT></TD></TR></TBODY></TABLE></CENTER><BR><BR>The =
middle key,=20
85, rises to the index page. Unfortunately, the index page is also full, =
so we=20
split the index page: <BR><BR>
<CENTER>
<TABLE border=3D1 cellPadding=3D5>
  <TBODY>
  <TR>
    <TH>Left Index Page</TH>
    <TH>Right Index Page</TH>
    <TH>New Index Page</TH></TR>
  <TR>
    <TD><TT>25 50 </TT></TD>
    <TD><TT>75 85</TT></TD>
    <TD>60</TD></TR></TBODY></TABLE></CENTER><BR><BR>The following table =
illustrates=20
the addition of the record containing 95 to the B+ tree. <BR><BR>
<CENTER>
<TABLE border=3D1 cellPadding=3D5>
  <CAPTION>Add Record with Key 95 </CAPTION>
  <TBODY>
  <TR>
    <TD><IMG border=3D0=20
      =
src=3D"http://www.iwu.edu/~sander/C314-Lectures/physicalDB/btree6.jpeg"> =

  </TD></TR></TBODY></TABLE></CENTER><BR><BR><B>Rotation</B> <BR><BR>B+ =
trees can=20
incorporate rotation to reduce the number of page splits. A rotation =
occurs when=20
a leaf page is full, but one of its sibling pages is not full. Rather =
than=20
splitting the leaf page, we move a record to its sibling, adjusting the =
indices=20
as necessary. Typically, the left sibling is checked first (if it =
exists) and=20
then the right sibling.=20
<P>As an example, consider the B+ tree before the addition of the record =

containing a key of 70. As previously stated this record belongs in the =
leaf=20
node containing 50 55 60 65. Notice that this node is full, but its left =
sibling=20
is not. <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>Using rotation we shift the =
record=20
with the lowest key to its sibling. Since this key appeared in the index =
page we=20
also modify the index page. The new B+ tree appears in the following =
table.=20
<BR><BR>
<CENTER>
<TABLE border=3D1 cellPadding=3D5>
  <CAPTION>Illustration of Rotation </CAPTION>
  <TBODY>
  <TR>
    <TD><IMG border=3D0=20
      =
src=3D"http://www.iwu.edu/~sander/C314-Lectures/physicalDB/btree7.jpeg"> =

  </TD></TR></TBODY></TABLE></CENTER><BR><BR><B>Deleting Keys from a B+ =
tree</B>=20
<BR><BR>We must consider three scenarios when we delete a record from a =
B+ tree.=20
Each scenario causes a different action in the delete algorithm. The =
scenarios=20
are: <BR><BR>
<CENTER>
<TABLE border=3D1 cellPadding=3D5>
  <CAPTION>The <TT>delete</TT> algorithm for B+ Trees</CAPTION>
  <TBODY>
  <TR>
    <TH>Leaf Page Below Fill Factor</TH>
    <TH>Index Page Below Fill Factor</TH>
    <TH>Action</TH></TR>
  <TR>
    <TD>NO </TD>
    <TD>NO</TD>
    <TD>Delete the record from the leaf page. Arrange keys in ascending =
order=20
      to fill void. If the key of the deleted record appears in the =
index page,=20
      use the next key to replace it.</TD></TR>
  <TR>
    <TD>YES</TD>
    <TD>NO</TD>
    <TD>
      <OL>Combine the leaf page and its sibling. Change the index page =
to=20
        reflect the change. </OL></TD>
  <TR>
    <TD>YES</TD>
    <TD>YES</TD>
    <TD>
      <OL>
        <LI>Combine the leaf page and its sibling.=20
        <LI>Adjust the index page to reflect the change.=20
        <LI>Combine the index page with its sibling. <BR><BR>Continue =
combining=20
        index pages until you reach a page with the correct fill factor =
or you=20
        reach the root page. =
</LI></OL></TD></TR></TBODY></TABLE></CENTER><BR><BR>As our=20
example, we consider the B+ tree after we added 95 as a key. As a =
refresher this=20
tree is printed in the following table. <BR><BR>
<CENTER>
<TABLE border=3D1 cellPadding=3D5>
  <CAPTION>Add Record with Key 95 </CAPTION>
  <TBODY>
  <TR>
    <TD><IMG border=3D0=20
      =
src=3D"http://www.iwu.edu/~sander/C314-Lectures/physicalDB/btree6.jpeg"> =

  </TD></TR></TBODY></TABLE></CENTER><BR><BR><B>Delete 70 from the B+ =
Tree</B>=20
<BR><BR>We begin by deleting the record with key 70 from the B+ tree. =
This=20
record is in a leaf page containing 60, 65 and 70. This page will =
contain 2=20
records after the deletion. Since our fill factor is 50% or (2 records) =
we=20
simply delete 70 from the leaf node. The following table shows the B+ =
tree after=20
the deletion. <BR><BR>
<CENTER>
<TABLE border=3D1 cellPadding=3D5>
  <CAPTION>Delete Record with Key 70 </CAPTION>
  <TBODY>
  <TR>
    <TD><IMG border=3D0=20
      =
src=3D"http://www.iwu.edu/~sander/C314-Lectures/physicalDB/btree8.jpeg"> =

  </TD></TR></TBODY></TABLE></CENTER><BR><BR><B>Delete 25 from the B+ =
tree</B>=20
<BR><BR>Next, we delete the record containing 25 from the B+ tree. This =
record=20
is found in the leaf node containing 25, 28, and 30. The fill factor =
will be 50%=20
after the deletion; however, 25 appears in the index page. Thus, when we =
delete=20
25 we must replace it with 28 in the index page.=20
<P>The following table shows the B+ tree after this deletion. <BR><BR>
<CENTER>
<TABLE border=3D1 cellPadding=3D5>
  <CAPTION>Delete Record with Key 25 </CAPTION>
  <TBODY>
  <TR>
    <TD><IMG border=3D0=20
      =
src=3D"http://www.iwu.edu/~sander/C314-Lectures/physicalDB/btree9.jpeg"> =

  </TD></TR></TBODY></TABLE></CENTER><BR><BR><B>Delete 60 from the B+ =
tree</B>=20
<BR><BR>As our last example, we're going to delete 60 from the B+ tree. =
This=20
deletion is interesting for several resasons:=20
<OL>
  <LI>The leaf page containing 60 (60 65) will be below the fill factor =
after=20
  the deletion. Thus, we must combine leaf pages.=20
  <LI>With recombined pages, the index page will be reduced by one key. =
Hence,=20
  it will also fall below the fill factor. Thus, we must combine index =
pages.=20
  <LI>Sixty appears as the only key in the root index page. Obviously, =
it will=20
  be removed with the deletion. </LI></OL><BR><BR>The following table =
shows the B+=20
tree after the deletion of 60. Notice that the tree contains a single =
index=20
page. <BR><BR>
<CENTER>
<TABLE border=3D1 cellPadding=3D5>
  <CAPTION>Delete Record with Key 60 </CAPTION>
  <TBODY>
  <TR>
    <TD><IMG border=3D0=20
      =
src=3D"http://www.iwu.edu/~sander/C314-Lectures/physicalDB/btree10.jpeg">=
=20
  </TD></TR></TBODY></TABLE></CENTER><BR><BR></BODY></HTML>

------=_NextPart_000_0000_01C140F7.A0D64020
Content-Type: image/jpeg
Content-Transfer-Encoding: base64
Content-Location: http://www.iwu.edu/~sander/C314-Lectures/physicalDB/btree3.jpeg

/9j/4AAQSkZJRgABAgEASABIAAD/7QG4UGhvdG9zaG9wIDMuMAA4QklNA+kAAAAAAHgAAwAAAEgA
SAAAAAAC2gIo/+H/4gL5AkYDRwUoA/wAAgAAAEgASAAAAAAC2gIoAAEAAABkAAAAAQADAwMAAKQC
AAEnDwABAAEAAAAAAAAAAAAAAAAAAgAAAAAAAAAAAEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA4
QklNA+0AAAAAABAASAAAAAEAAQBIAAAAAQABOEJJTQPzAAAAAAAIAAAAAAAAAAA4QklNJxAAAAAA
AAoAAQAAAAAAAAACOEJJTQP1AAAAAABIAC9mZgABAGxmZgAGAAAAAAABAC9mZgABAKGZmgAGAAAA
AAABADIAAAABAFoAAAAGAAAAAAABADUAAAABAC0AAAAGAAAAAAABOEJJTQP4AAAAAABwAAD/////
////////////////////////A+gAAAAA/////////////////////////////wPoAAAAAP//////
//////////////////////8D6AAAAAD/////////////////////////////A+gAADhCSU0EBgAA
AAAAAgAC/+4ADkFkb2JlAGSAAAAAAf/bAIQADAgICAkIDAkJDBELCgsRFQ8MDA8VGBMTFRMTGBEM