数据排序10.31日

《数据排序10.31日》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、查找：这一章，需要识记关键字、主关键字、次关键字的含义;静态查找与动态查找的含义及区别;平均查找长度ASL的概念念及在各种查找算法中的计算方法和计算结果，特别是一些典型结构的ASL值，B-树的概念和基本操作冲突解决方法的选择和冲突处理过程的描述，B+树的概念(新增考点)，特别要注意B-树和B+树概念的对比，以及Hash表相关的概念。要熟练掌握顺序表、链表、二叉树上的查找方法，特别要注意顺序查找、二分查找的适用条件(比如链表上用二分查找就不合适)和算法复杂度。B树和B-树是同一种树，只不过英语中B

2、-tree被中国人翻译成了B-树，让人以为B树和B-树是两种树，实际上，两者就是同一种树.第一节、B树、B+树、B*树1.前言：但是咱们有面对这样一个实际问题：就是大规模数据存储中，实现索引查询这样一个实际背景下，树节点存储的元素数量是有限的（如果元素数量非常多的话，查找就退化成节点内部的线性查找了），这样导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下（为什么会出现这种情况，待会在外部存储器-磁盘中有所解释），那么如何减少树的深度（当然是不能减少查询的数据量

3、），一个基本的想法就是：采用多叉树结构（由于树节点元素数量是有限的，自然该节点的子树数量也就是有限的）。这样我们就提出了一个新的查找树结构——多路查找树。根据平衡二叉树的启发，自然就想到平衡多路查找树结构，也就是这篇文章所要阐述的第一个主题B~tree(B树结构)。B-tree（B-tree树即B树）在开始介绍B~tree之前，先了解下相关的硬件知识，才能很好的了解为什么需要B~tree这种外存数据结构。  所以，在大规模数据存储方面，大量数据存储在外存磁盘中，而在外存磁盘中读取/写入块(blo

4、ck)27/27中某数据时，首先需要定位到磁盘中的某块，如何有效地查找磁盘中的数据，需要一种合理高效的外存数据结构，就是下面所要重点阐述的B-tree结构，以及相关的变种结构：B+-tree结构和B*-tree结构。3.B-树  具体讲解之前，有一点，再次强调下：B-树，即为B树。因为B树的原英文名称为B-tree，而国内很多人喜欢把B-tree译作B-树，其实，这是个非常不好的直译，很容易让人产生误解。如人们可能会以为B-树是一种树，而B树又是一种一种树。而事实上是，B-tree就是指的B树。

5、特此说明。我们知道，B树是为了磁盘或其它存储设备而设计的一种多叉（下面你会看到，相对于二叉，B树每个内结点有多个分支，即多叉）平衡查找树。与本blog之前介绍的红黑树很相似，但在降低磁盘I/0操作方面要更好一些。许多数据库系统都一般使用B树或者B树的各种变形结构，如下文即将要介绍的B+树，B*树来存储信息。 B树与红黑树最大的不同在于，B树的结点可以有许多子女，从几个到几千个。那为什么又说B树与红黑树很相似呢?因为与红黑树一样，一棵含n个结点的B树的高度也为O（lgn），但可能比一棵红黑树的高度

6、小许多，应为它的分支因子比较大。所以，B树可以在O（logn）时间内，实现各种如插入（insert），删除（delete）等动态集合操作。如下图所示，即是一棵B树，一棵关键字为英语中辅音字母的B树，现在要从树种查找字母R（包含n[x]个关键字的内结点x，x有n[x]+1]个子女（也就是说，一个内结点x若含有n[x]个关键字，那么x将含有n[x]+1个子女）。所有的叶结点都处于相同的深度，带阴影的结点为查找字母R时要检查的结点）： 27/27相信，从上图你能轻易的看到，一个内结点x若含有n[x]个

7、关键字，那么x将含有n[x]+1个子女。如含有2个关键字DH的内结点有3个子女，而含有3个关键字QTX的内结点有4个子女。B树又叫平衡多路查找树。一棵m阶的B树(m叉树)的特性如下：1.树中每个结点最多含有m个孩子（m>=2）；2.除根结点和叶子结点外，其它每个结点至少有[ceil(m/2)]个孩子（其中ceil(x)是一个取上限的函数）；3.若根结点不是叶子结点，则至少有2个孩子（特殊情况：没有孩子的根结点，即根结点为叶子结点，整棵树只有一个根节点）；4.所有叶子结点都出现在同一层，叶子结点不

8、包含任何关键字信息(可以看做是外部接点或查询失败的接点，实际上这些结点不存在，指向这些结点的指针都为null)；5.每个非终端结点中包含有n个关键字信息：(n，P0，K1，P1，K2，P2，......，Kn，Pn)。其中：      a)  Ki(i=1...n)为关键字，且关键字按顺序升序排序K(i-1)