好贷网好贷款

查找算法总结(三)

发布时间:2016-12-4 16:15:48 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"查找算法总结(三)",主要涉及到查找算法总结(三)方面的内容,对于查找算法总结(三)感兴趣的同学可以参考一下。

六、多路查找树、B~树、B+树       B树一种多路查找树(维基百科中定义):存储排序数据并允许以O(log n)的运行时间进行查找,顺序读取,插入和删除的数据结构。B树,概括来说是一个节点可以拥有多于2个子节点的二叉查找树。也可以说是 B- 或 B~树。      术语B树可以指一个特定的方案,也可以指大体上一类方案。狭义上,一个B树在它内部节点中存储键值,但不需在叶子节点上存储这些键值的记录。大体上的一类包含一些变体,如B+树或B*树。 【B~ 树】       B- 树,又叫做平衡多路查找树,一颗 m 阶的B- 树 (也可以说是m叉树) 的特征如下: 1、树中每个结点最多有 m 个孩子; 2、除根结点和叶子节点外,其他每个节点至少有 m / 2 个孩子; 3、若根结点不是叶子节点,则至少有 2 个孩子; 4、所有叶子结点都出现在同一层,叶子结点不包含任何关键字信息 5、每个非终结点中包含 n 个关键字信息:(n, P0, K1, P1, K2, P2, ... , Kn, Pn)。其中,      a、Ki(i=1...n)为关键字,且关键字按顺序排序Ki < K(i-1)      b、Pi为指向子树的结点,且指针P(i-1)指向子树中所有结点的关键字均小于Ki,但是大于K(i-1)      c、关键字的个数 n 必须满足:m/2 - 1 <= n <= m-1 6、有n棵子树的结点中含有 n-1 个关键字(即K所表示i的内容)      关于b所述的内容,一直没有理解明白,后来还是通过这张图才理解,此图中我省略了一些节点,仅仅画出了Pi指向的那个节点,这个节点中的关键字全部都是大于K(i-1),并且小于Ki 的。(注意:P 的个数 比 K 的个数多 1 个) 举例分析:下面就是一棵3阶B~树 (为了简单,这里用少量数据构造一棵2-4树的形式,其实实际应用中的B树结点中关键字很多的) 现在我们模拟查找文件29的过程:       (1) 根据根结点指针找到文件目录的根磁盘块1,将其中的信息导入内存。【磁盘IO操作1次】       (2) 此时内存中有两个文件名17,35和三个存储其他磁盘页面地址的数据。根据算法我们发现17<29<35,因此我们找到指针p2。       (3) 根据p2指针,我们定位到磁盘块3,并将其中的信息导入内存。【磁盘IO操作2次】       (4) 此时内存中有两个文件名26,30和三个存储其他磁盘页面地址的数据。根据算法我们发现26<29<30,因此我们找到指针p2。       (5) 根据p2指针,我们定位到磁盘块8,并将其中的信息导入内存。【磁盘IO操作3次】      (6) 此时内存中有两个文件名28,29。根据算法我们查找到文件29,并定位了该文件内存的磁盘地址。 分析一下上面的过程,      我们发现需要3次磁盘IO操作和3次内存查找操作。关于内存中的文件名查找,由于是一个有序表结构,可以利用折半查找提高效率。至于3次磁盘IO操作时影响整个B~树查找效率的决定因素。       当然,如果我们使用平衡二叉树的磁盘存储结构来进行查找,磁盘IO操作最少4次,最多5次。而且文件越多,B~树比平衡二叉树所用的磁盘IO操作次数将越少,效率也越高。 【B+树】 B+ 树 是应文件系统所需而产生的中B~树的变形树。B+ 树元素自底向上插入,这与二叉树恰好相反。 一颗 m 阶的B+树和 m 阶的B-树的异同在于:      1、有n棵子树的结点中含有 n - 1个关键字; (与B 树n棵子树有n-1个关键字相同)      2、所有叶子节点包含了全部的关键字信息,及指向含有这些关键字记录的指针,且叶子结点本身依关键字的大小从小到大的顺序链接。(而B树的叶子结点并没有包含全部需要查找的信息)      3、所有非终结点都可以看出是索引部分,结点中仅含有其子树根结点中最大或最下关键字。(B树的非终结点也包含需要查找的有效信息)       B+树的内部结点并没有指向关键字具体信息的指针(而B树则会包括,因为B树内部结点包含关键字信息),这样就会导致B+树的内部结点相对于B树来说小一些。如果把同一个内部结点的关键字存放在同一个盘块儿中, 那么盘块儿所能容纳的关键字数量也就越多,那么一次性读入内存中的需要查找的关键字也就越多,相对来说IO读写次数就会减少。      举个例子吧:      假设磁盘中一个盘块儿容纳16bytes,而一个关键字是2bytes,一个关键字具体信息指针是2bytes。      一棵9阶B~树(一个结点最多8个关键字)的内部结点需要2个盘快。而B+树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候,B~树就比B+数多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。      如果没有明白,再详细的分析一下:假设树是这样的。  假设这个是 9阶 B树或B+树的某个节点,那么这个节点至少有 9/2 个孩子, 最多有9个孩子。      如果是B树的情况下:      当有9个孩子的时候,则有8个关键字(n-1的关系),同时也具有8个关键字具体信息的指针(这些指针用来指向这个关键字在这个内部结点存储的位置,例如上面B树中的小红色块儿区域),如果我们只保存这个内部结点的信息,需要的存储空间是 9*2 + 8*2 + 8*2 = 50(bytes); 当有4个孩子的时候,则有3个关键字,同时也具有3个关键字具体信息的指针,内部结点需要的存储空间是 4*2 + 3*2 + 3*2 = 20(bytes)。所以这个内部节点最少需要20bytes(即2个盘块儿),最多需要50bytes(即4个盘块儿)。      如果是B+树的情况下:      当有9个孩子的时候,则有8个关键字,但是没有8个关键字的具体信息指针,那么内部结点需要的内存空间是 9*2 + 8*2 = 34(bytes);当有4个孩子的时候,则有3个关键字,但是没有3个关键字的具体信息指针,那么内部结点需要的内存空间是4*2 + 3*2 = 14(bytes)。所以这个内部结点最少需要14bytes(即1个盘块儿),最多需要34bytes(即3个盘块儿)。            从上面的分析中就可以看出,无论怎样,在相同的条件下,即无论是B树还是B+树,在这个内部节点有相同的孩子树的时候,读取这个内部节点信息的时候,B树进行的IO操作会多一些。       为什么说B+-tree比B 树更适合实际应用中操作系统的文件索引和数据库索引?      第一点就是刚刚我们再上面所讲到的内容:即B+树的磁盘读写代价更低;      第二点就是B+树的查询效率更加稳定。           第二点怎么解释呢?由于非终结点并不是最终指向文件内容的结点(即没有存储关键字的具体信息),而只是存储叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根节点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率都相当。 B+树相对于B树的优点:      1、B+树非常容易扫库,即很容易查询出所有的数据,直接从叶子结点挨个扫一遍句完事儿了,但是B树必须用中序遍历的方法进行遍历;      2、B+树支持range-query非常方便,而B树不支持。这是数据库选用B+树的最主要原因。      比如要查 5-10之间的,B+树一把到5这个标记,再一把到10,然后串起来就行了,B树就非常麻烦。B树的好处,就是成功查询特别有利,因为树的高度总体要比B+树矮。不成功的情况下,B树也比B+树稍稍占一点点便宜。     B树比如你的例子中查,17的话,一把就得到结果了,有很多基于频率的搜索是选用B树,越频繁query的结点越往根上走,前提是需要对query做统计,而且要对key做一些变化。         另外B树也好B+树也好,根或者上面几层的节点因为被反复query,所以这几块基本都在内存中,不会出现读磁盘IO,一般在启动的时候,就会主动放入内存。  【B* 树】 B*-tree是B+-tree的变体,在B+树的基础上(所有的叶子结点中包含了全部关键字的信息,及指向含有这些关键字记录的指针),B*树中非根和非叶子结点再增加指向兄弟的指针;B*树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为2/3(代替B+树的1/2)。给出了一个简单实例,如下图所示:       B+树的分裂:当一个结点满时,分配一个新的结点,并将原结点中1/2的数据复制到新结点,最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针。       B*树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针。      所以,B*树分配新结点的概率比B+树要低,空间使用率更高; 几种查找算法分析就分析到这里,我也是根据几篇文章进行总结的,其中大部分的内容来自于爪哇人的博客和结构算法 算法之道的博客,对于一些比较难懂的内容,又添加了自己的分析,如有问题,可以留下评论一起讨论。

上一篇:Java编程技术中汉字问题的分析及解决
下一篇:jQuery EasyUI API 中文文档 - 链接按钮(linkbutton)

相关文章

相关评论