1 Introduction

1.1 Intro

参考[search introduction]的介绍.

散列检索, 用以提高检索效率, 大部分情况下是面向用户的操作, 根据用户的输入来进行快速
的检索, 并尽可能快速的给出结果.
在这种要求下, 如何存储数据? 以怎样的结构来构造?如何避免冲突?如何解决检索的唯一性?
这些都是散列检索需要解决的问题.

1.2 Classify

  • 静态索引: 在初始阶段, 索引结构已经固定下来, 整个存储结构是固定的
  • 动态索引: 在系统运行过程, 索引本身会一直在变化

1.3 性能分析

平均检索长度: 决定了查找的性能

负载因子: a = N/M, 其中N表示源数据, M 表示散列表存储空间, 其中a越大, 则表示发生冲突的可能性越高, 很多记录偏离基地址的可能性越大.

2 B-tree

2.1 Intro

B-tree的提出基于以下的背景:

1
2
3
4
5
对于大规模的数据存储, 如果使用二叉查找树, 那么该存储
结构的深度会非常之高, 如果此时查找的数值在一个h非常大的地方,
那么需要经过很多次的磁盘 IO才能达到最终目的, 从而降低了性能.

只有降低 h, 才能减少 IO 次数, 故而采取了多阶数结构, 从而提出 B-tree.

B-tree: 保持树结构较低的高度, 避免磁盘过于频繁的查找存取操作(同一个节点里面的key可以顺序存储在磁盘上), 有效的提高检索效率. 实际上, 每个结点包含大量的关键字信息和分支,
当然不能超过磁盘块的大小(一般为1k~4k), 这样根据磁盘读取的原理, 每次读取一个磁盘块就
相当于读取一个结点, 大大的提高效率.

B-tree定义(m分叉):

  • 根节点至少包含两个子节点, 除非仅仅存在一个根节点
  • 每个节点至多有m个子结点, 每一个内结点至多有[ceil(m/2)]个孩子(向上取整).
  • 所有的叶子结点都处于相同的深度
  • 如果某一个内结点(非root, 非叶子), 若该结点含有s个键值, 那么该结点一定存在s+1个子节点

2.2 检索

  • 根节点读出并将其中关键码与查找值比较

    1. 如果找到, 则检索成功
    2. 否则找到当前结点ki~ki+1之间的pi, 进入子树
  • 重复上述步骤, 递归, 知道找到或者pi为空(叶子结点)时停止

如果树高为h, 则需要h次读索引盘 + 由关键码中隐含指针找到记录主文件位置的一次读盘

2.3 插入

  • 检索是否存在, 如果存在, 直接决绝, 返回索引位置__
  • 最后定位的叶子结点为待插入的位置
  • 插入完成后

    1. 叶子结点关键码个数小于m, 则插入完成, 直接返回__
    2. 叶子结点关键码个数等于m, 产生上溢出(key过多), 取这m个关键码的中位数, 分裂为左右孩子
  • 将中位数分解码插入到父节点中, 如果父节点未上溢出, 则返回__

  • 继承上面的步骤, 一直往根节点递归传递, 其中根节点允许的子结点数在2~m-1之间.

2.4 删除

  • 如果删除的关键码x不在叶节点层, 则将此关键码与后继结点对换位置, 即将右指针子树中的最左的叶子结点提到当前位置, 同时删除x.
  • 如果删除后产生下溢出(最小元素数目为ceil(m/2)), 需要向父节点借一个节点, 将最丰满的相邻兄弟结点中上移最后或最前一个元素到父节点中(类似左旋操作).

删除R 元素:

delete1

调整, W 下移, X 上移:

delete2