?? page344.html
字號:
<HTML><HEAD><TITLE>Inserting Items into a B-Tree</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html5154" HREF="page345.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5152" HREF="page340.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5146" HREF="page343.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5156" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0010720000000000000000">Inserting Items into a B-Tree</A></H2><P>The algorithm for insertion into a B-Tree beginsas do all the other search tree insertion algorithms:To insert item <I>x</I>,we begin at the root and conduct a search for it.Assuming the item is not already in the tree,the unsuccessful search will terminate at a leaf node.This is the point in the tree at which the <I>x</I> is inserted.<P>If the leaf node has fewer than <I>M</I>-1 keys in it,we simply insert the item in the leaf node and we are done.For example, consider a leaf node with <I>n</I><I><</I><I>M</I> subtrees and <I>n</I>-1 keys of the form<P> <IMG WIDTH=385 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath65041" SRC="img1338.gif" ><P>For every new key inserted in the node,a new subtree is required too.In this case because <I>T</I> is a leaf,all its subtrees are empty trees.Therefore, when we insert item <I>x</I>,we really insert the pair of items <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65061" SRC="img1339.gif" >.Suppose the key to be inserted falls between <IMG WIDTH=12 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63737" SRC="img1177.gif" > and <IMG WIDTH=26 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline64781" SRC="img1304.gif" >,i.e., <IMG WIDTH=92 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline63803" SRC="img1182.gif" >.When we insert the pair <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65061" SRC="img1339.gif" > into <I>T</I>we get the new leaf <I>T</I>' given by<P> <IMG WIDTH=475 HEIGHT=17 ALIGN=BOTTOM ALT="displaymath65042" SRC="img1340.gif" ><P><P>What happens when the leaf is full?That is, suppose we wish to insert the pair, <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65061" SRC="img1339.gif" > into a node <I>T</I> which already has <I>M</I>-1 keys.Inserting the pair in its correct position gives a result of the form<P> <IMG WIDTH=376 HEIGHT=17 ALIGN=BOTTOM ALT="displaymath65043" SRC="img1341.gif" ><P>However, this is not a valid node in a B-tree of order <I>M</I>because it has <I>M</I>+1 subtrees and <I>M</I> keys.The solution is to split node <I>T</I>' in half as follows<P> <IMG WIDTH=500 HEIGHT=42 ALIGN=BOTTOM ALT="eqnarray21302" SRC="img1342.gif" ><P>Note, <IMG WIDTH=18 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65089" SRC="img1343.gif" > is a valid B-tree node because it contains <IMG WIDTH=41 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64977" SRC="img1328.gif" > subtrees and <IMG WIDTH=71 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65005" SRC="img1331.gif" > keys.Similarly, <IMG WIDTH=18 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65095" SRC="img1344.gif" > is a valid B-tree node because it contains <IMG WIDTH=83 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65097" SRC="img1345.gif" > subtrees and <IMG WIDTH=111 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65099" SRC="img1346.gif" > keys.Note that there is still a key left over,namely <IMG WIDTH=43 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65101" SRC="img1347.gif" >.<P>There are now two cases to consider--either <I>T</I> is the root or it is not.Suppose <I>T</I> is not the root.Where we once had the single node <I>T</I>,we now have the two nodes, <IMG WIDTH=18 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65089" SRC="img1343.gif" > and <IMG WIDTH=18 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65095" SRC="img1344.gif" >,and the left-over key, <IMG WIDTH=43 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65101" SRC="img1347.gif" >.This situation is resolved as follows:First, <IMG WIDTH=18 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65089" SRC="img1343.gif" > replaces <I>T</I> in the parent of <I>T</I>.Next, we take the pair <IMG WIDTH=83 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65121" SRC="img1348.gif" >and recursively insert it in the parent of <I>T</I>.<P>Figure <A HREF="page344.html#figbtree2"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> illustrates this case for a B-tree of order three.Inserting the key 6 in the tree causes the leaf node to overflow.The leaf is split in two.The left half contains key 5; and the right, key 7; and key 6 is left over.The two halves are re-attached to the parent in the appropriate placewith the left-over key between them.<P><P><A NAME="21555"> </A><A NAME="figbtree2"> </A> <IMG WIDTH=575 HEIGHT=502 ALIGN=BOTTOM ALT="figure21315" SRC="img1349.gif" ><BR><STRONG>Figure:</STRONG> Inserting items into a B-tree (insert 6).<BR><P><P>If the parent node fills up,then it too is split and the two new nodes are inserted in the grandparent.This process may continue all the way up the tree to the root.What do we do when the root fills up?When the root fills, it is also split.However, since there is no parent into which to insert the two new children,a new root is inserted above the old root.The new root will contain exactly two subtrees and one key,as allowed by Definition <A HREF="page340.html#defnbtree"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P>Figure <A HREF="page344.html#figbtree3"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> illustrates this case for a B-tree of order three.Inserting the key 3 in the tree causes the leaf node to overflow.Splitting the leaf and reattaching it causes the parent to overflow.Similarly, splitting the parent and reattaching it causes the grandparentto overflow but the grandparent is the root.The root is split and a new root is added above it.<P><P><A NAME="21996"> </A><A NAME="figbtree3"> </A> <IMG WIDTH=575 HEIGHT=833 ALIGN=BOTTOM ALT="figure21560" SRC="img1350.gif" ><BR><STRONG>Figure:</STRONG> Inserting items into a B-tree (insert 3).<BR><P><P>Notice that the height of the B-tree only increases when the root node splits.Furthermore, when the root node splits,the two halves are both attached under the new root.Therefore, the external nodes all remain at the same depth,as required by Definition <A HREF="page340.html#defnbtree"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P><BR> <HR><UL> <LI> <A NAME="tex2html5157" HREF="page345.html#SECTION0010721000000000000000">Implementation</A><LI> <A NAME="tex2html5158" HREF="page346.html#SECTION0010722000000000000000">Running Time Analysis</A></UL><HR><A NAME="tex2html5154" HREF="page345.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5152" HREF="page340.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5146" HREF="page343.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5156" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -