数据库中需要引用查找结构,为了更加迅速的查找硬盘中的数据库,因为硬盘IO的速度非常的耗时,所以要尽量选择能够将IO次数减少的数据结构,下面一个个分析动态查找结构,找到最合适的结构.

二叉排序树(二叉查找树,二叉搜索树)

二叉排序树(Binary Sort Tree)又称二叉查找树(Binary Search Tree),亦称二叉搜索树。 它或者是一棵空树;或者是具有下列性质的二叉树:

  1. 若左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  2. 若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值;
  3. 左、右子树也分别为二叉排序树;

它的查找复杂度 P(n)=O(logn)

这里就不讲它的插入,删除操作了

可以看到二叉排序树是最简单的一种动态查找结构,它对树的深度没有进行优化,这就使得树深有可能非常的大(最坏情况树深=节点数).

平衡二叉树

平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。构造与调整方法 平衡二叉树的常用算法有红黑树、AVL、Treap等。 最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列,可以参考Fibonacci数列,1是根节点,F(n-1)是左子树的节点数量,F(n-2)是右子树的节点数量。

平衡二叉树通过旋转可以使树深不至于太大,它的平均查找长度也是logn,但它能有效避免二叉排序树的那种极端情况出现.

B-tree

这里B-tree不是B减树而是叫做B树

对于上面两种树形结构,它们的树深往往太深,对于海量数据而言简直是个灾难,所以有人发明了B-tree,它是一个多路查找树,很轻易的就减小了树深.

一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树,或者是满足下列性质的树:

  1. 根结点至少有两个子女;
  2. 每个非根节点所包含的关键字个数 j 满足:┌m/2┐ - 1 <= j <= m - 1;
  3. 除根结点以外的所有结点(不包括叶子结点)的度数正好是关键字总数加1,故内部子树个数 k 满足:┌m/2┐ <= k <= m ;
  4. 所有的叶子结点都位于同一层。

在B-树中,每个结点中关键字从小到大排列,并且当该结点的孩子是非叶子结点时,该k-1个关键字正好是k个孩子包含的关键字的值域的分划。

因为叶子结点不包含关键字,所以可以把叶子结点看成在树里实际上并不存在外部结点,指向这些外部结点的指针为空,叶子结点的数目正好等于树中所包含的关键字总个数加1。

下面,咱们来模拟下查找文件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次内存查找操作。关于内存中的文件名查找,由于是一个有序表结构,可以利用折半查找提高效率。至于IO操作是影响整个B树查找效率的决定因素。

当然,如果我们使用平衡二叉树的磁盘存储结构来进行查找,磁盘4次,最多5次,而且文件越多,B树比平衡二叉树所用的磁盘IO操作次数将越少,效率也越高。

B+tree

对于B-tree,所有节点都会带有指向其关键字的指针(途中红色小方块),这样做有利于加快查找速度,但是还有个缺点,就是会加大节点存储空间,造成盘块读取的增加,导致增加硬盘IO;而B+tree则取消掉这个红块,所有的关键字和关键字指针都存在叶子节点中,每次查找都会遍历到B+tree的底部(不管查找到还是没查找到),增加了查询深度的稳定,还有一点就是它解决了元素遍历效率底下的问题,就是说它的叶子节点链接成一个链表,可以有效的进行链表遍历.

B+tree是应文件系统所需而产生的一种B-tree的变形树。

一棵m阶的B+树和m阶的B树的异同点在于:

  1. 有n棵子树的结点中含有n-1 个关键字; (此处颇有争议,B+树到底是与B 树n棵子树有n-1个关键字 保持一致,还是不一致:B树n棵子树的结点中含有n个关键字,待后续查证。暂先提供两个参考链接:①wikipedia http://en.wikipedia.org/wiki/B%2B_tree#Overview;②http://hedengcheng.com/?p=525。而下面B+的图尚未最终确定是否有问题,请读者注意)
  2. 所有的叶子结点中包含了全部关键字的信息,及指向含有这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大的顺序链接。 (而B 树的叶子节点并没有包括全部需要查找的信息)
  3. 所有的非终端结点可以看成是索引部分,结点中仅含有其子树根结点中最大(或最小)关键字。 (而B 树的非终节点也包含需要查找的有效信息)