📄 page330.html
字号:
<HTML><HEAD><TITLE>M-Way Search Trees</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="tex2html4994" HREF="page331.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4992" HREF="page298.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4986" HREF="page329.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4996" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION0010600000000000000000"><I>M</I>-Way Search Trees</A></H1><P>As defined in Section <A HREF="page300.html#secsrchtreemwaytree"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,an internal node of an <I>M</I>-way search tree contains <I>n</I> subtrees and <I>n</I>-1 keys,where <IMG WIDTH=76 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63729" SRC="img1173.gif" >, for some fixed value of <IMG WIDTH=45 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64641" SRC="img1293.gif" >.The preceding sections give implementations for the special casein which the fixed value of <I>M</I>=2 is assumed (binary search trees).In this section,we consider the implementation of <I>M</I>-way search treesfor <em>arbitrary</em>, larger values of <IMG WIDTH=48 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline64647" SRC="img1294.gif" >.<P>Why are we interested in larger values of <I>M</I>?Suppose we have a very large data set--so large that we cannot get it all intothe main memory of the computer at the same time.In this situation we implement the search tree in secondary storage,i.e., on disk.The unique characteristics of disk-based storage<em>vis-à-vis</em> memory-based storagemake it necessary to use larger values of <I>M</I>in order to implement search trees efficiently.<P>The typical disk access time is 1-10 ms,whereas the typical main memory access time is 10-100 ns.Thus, main memory accesses are between 10000 and 1000000 timesfaster than typical disk accesses.Therefore to maximize performance,it is imperative that the total number of disk accesses be minimized.<P>In addition, disks are block-oriented devices.Data are transfered between main memory and disk in large blocks.The typical block sizes are between 512 bytes and 4096 bytes.Consequently, it makes sense to organize the data structure to take advantageof the ability to transfer entire blocks of data efficiently.<P>By choosing a suitably large value for <I>M</I>,we can arrange that one node of an <I>M</I>-way search treeoccupies an entire disk block.If every internal node in the <I>M</I>-way search tree has exactly <I>M</I> children,we can use Theorem <A HREF="page256.html#theoremtreesii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> todetermine the height of the tree:<P><A NAME="eqnsrchtreemway"> </A> <IMG WIDTH=500 HEIGHT=16 ALIGN=BOTTOM ALT="equation20391" SRC="img1295.gif" ><P>where <I>n</I> is the number of internal nodes in the search tree.A node in an <I>M</I>-way search tree that has <I>M</I> childrencontains exactly <I>M</I>-1 keys.Therefore, altogether there are <I>K</I>=(<I>M</I>-1)<I>n</I> keys andEquation <A HREF="page330.html#eqnsrchtreemway"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> becomes <IMG WIDTH=159 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64671" SRC="img1296.gif" >.Ideally the search tree is well balancedand the inequality becomes an equality.<P>For example, consider a search tree which contains <IMG WIDTH=97 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline64673" SRC="img1297.gif" > keys.Suppose the size of a disk block is such that we can fita node of size <I>M</I>=128 in it.Since each node contains at most 127 keys,at least 16513 nodes are required.In the best case, the height of the <I>M</I>-way search tree is only twoand at most three disk accesses are required to retrieve any key!This is a significant improvement over a binary tree,the height of which is at least 20.<P><BR> <HR><UL> <LI> <A NAME="tex2html4997" HREF="page331.html#SECTION0010610000000000000000">Implementing <I>M</I>-Way Search Trees</A><LI> <A NAME="tex2html4998" HREF="page335.html#SECTION0010620000000000000000">Finding Items in an <I>M</I>-Way Search Tree</A><LI> <A NAME="tex2html4999" HREF="page338.html#SECTION0010630000000000000000">Inserting Items into an <I>M</I>-Way Search Tree</A><LI> <A NAME="tex2html5000" HREF="page339.html#SECTION0010640000000000000000">Removing Items from an <I>M</I>-Way Search Tree</A></UL><HR><A NAME="tex2html4994" HREF="page331.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4992" HREF="page298.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4986" HREF="page329.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4996" 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 + -