1 Introduction

1.1 Intro

在一组记录集合中找到关键码值等于给定值的某个记录, 或者找到关键码值符合特定条件的
某些记录的过程.

一般而言, 检索的数据对象都是大量的数据, 所以对检索的效率要求非常, 为了提高检索
效率, 需要在数据存储时做一些特殊的存储预处理, 以便在之后检索时更加快速.

classify

1.2 基本概念

  • 预排序: 在数据进行存储时, 进行一定的预处理, 以便检索更加快捷, 比如二分法查找就要求数据本身逻辑上是一棵树结构.
  • 建立索引: 以空间换时间, 充分利用索引来加快索引速度
  • 散列技术: 将数据组织到表中, 根据关键码来确定表中每一个记录的位置
  • ASL: 平均检索长度, 检索过程中对关键码需要执行的平均比较次数, 衡量检索算法优劣的时间标准

2 基于线性表的查找

2.1 Intro

基于线性表的查找, 其中数据的存储都是连续的, 在此物理存储的基础上提出的查找算法.

2.2 Classify

  • 顺序查找: 针对线性表中的记录, 逐个的进行关键码和给定值的比较
  • 二分查找: 首先是有序的, 之后在逻辑上使用二分查找
  • 分块查找: 顺序查找和二分查找的折衷

3 基于散列表的查找

3.1 Intro

何谓散列?

  • 一个确定的函数关系h
  • 以节点的key为自变量
  • 将h(key)作为结点的存储地址

基本概念:

  • 负载因子: a = n/m, 散列表空间大小m, 填入表中的结点数n
  • 冲突: 某些散列函数对于不等关键码计算出相同的散列地址.
  • 同义词: 发生冲突的两个关键码

散列技术的重要关注点:

  • 如何是结点分布均匀的散列函数?
  • 如何解决冲突?

3.2 Index

  • 线性索引: 一级索引, 二级索引
  • 静态索引: MWT, ISAM, 倒排
  • 动态索引: B 树, B++树, 红黑树, 其中 B 树其实也是 MWT 的一种

关于索引的信息介绍, 见第5张说明

3.3 散列函数

  • 除余法: h(x) = x mod M
  • 乘余取整法: hash ( key ) = ⎣ n ( A key % 1 ) ⎦
  • 平方取中法: 先通过求关键码的平方来扩大差别,再取其中的几位或其组合作为散列地址
  • 数字分析法:
  • 基数转换法: 把关键码转换成原来进制上的数, 取其中若干位作为散列地址
  • 折叠法: 将关键码分割成位数相同的几部分, 取这几部分的叠加和作为散列地址

3.4 碰撞处理

  • 开散列方法: 把发生冲突的关键码存储在散列表主表之外的一条链上
  • 闭散列方法: 开地址法, 把发生冲突的关键码存储在表中另一个槽内

3.5 拉链法

将所有关键字为同义词的结点链接在同一个单链表中, 若选定的散列表长度为m, 则可将散列表定义为一个由m个头指针组成的指针数组t[0..m-1].

凡是散列地址为i的结点, 均插入到以t为头指针的单链表中

open-zip

3.6 桶式散列

适合于存储于磁盘的散列表, 整体流程:

  • 把一个文件的记录分为若干存储桶, 每个存储桶包含一个或多个页块
  • 每一个存储桶内的各页块用指针连接起来, 每个页块包含若干记录
  • 散列函数h(K)表示具有关键码值K的记录所在的存储桶号

3.7 闭散列

当冲突发生时,使用某种方法为关键码K生成一个散列地址序列,

d0, d1, d2, ..., dm-1

其中d0为基地址(h(K)), di则为后继散列地址, 当然如果所有的后继散列地址都不空闲,
则说明闭散列表已满.

3.8 基本操作

删除

  • 删除一个记录一定不能影响后面的检索, 释放的存储位置应该能够为将来插入使用
  • 只有开散列方法可以真正的删除, 闭散列方法都只能作标记(墓碑)

插入:

  • 避免插入两个相同的关键码
  • 一旦碰到墓碑, 检索过程仍然需要沿着探查序列下去, 直到找到空位置

4 基于位图的查找

4.1 Intro

使用位向量, 为每一个可能的集合元素(0, n-1)分配一个bit位置, 根据bit来进行判断是
否存在.

其中在进行位运算的时候, 通常在遍历时并非一位位的进行操作, 而是按照基本数据类型长度
的位数来进行操作, 其中类似的 C 代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 对于存在41个元素的unsigned long数字集合
#define N = 41
typedef unsigned long ulong;
enum {
NB = 8*sizeof(ulong);
LI = N==0 ? 0 : (N-1)/NB;
}
ulong A[] = {35, 30, 9, 7}
ulong AB[LI + 1];

for (int i=0; i<N; i++) {
value = A[i];
// 右移 value % NB
AB[value/NB] = (ulong)1 << (value % NB);
}

4.2 位图索引

使用位图表示的索引, 对列的每个键值建立一个位图, 用于orcale数据库中, 相比 B 树索引,
占用的空间更小, 查找极快.

例如, 对于表test, 有一个state列, 总共10行数据:

1
2
3
4
5
6
7
数据: 10    20    30    20    10    30    10    30    20    30
此时会建立位图:
BLOCK1 KEY=10 1 0 0 0 1 0 1 0 0 0
BLOCK2 KEY=20 1 0 0 0 1 0 1 0 0 0
BLOCK3 KEY=30 1 0 0 0 1 0 1 0 0 0
也就是, 对相同值按照位数来进行存储表示, 当然 Block1的长度跟随记录的增加也
要进行调整.
  • 优点: 决策支持系统
  • 缺点: 键值较多的列, 重复较少的列实际上效率不高; 对于update, insert, delete频繁的列, 代价大

5 Index

5.1 Intro

广义上的索引–指针/链接, 实际上在线性查找(如二分), 散列查找(本身特质)都存在.
狭义上的索引–一般指散列查找中的索引.

5.2 线性索引

在线性索引中, 索引文件并组织成一组简单的键值对(key, value)的序列, 一般来说该序列
还是有序的.

线性索引中的这种结构, 能够实现高效的, 随机的访问, 就相当于对线性查找的一种优化
措施, 想想函数的分装, 其实思想大体类似.

对某一块数据, 确定唯一的索引, 检索时确定首先能够快速的确定块位置, 之后进入块内部
进行其他查找.

索引本身还存在一级索引, 二级索引, 多级索引.

互联网就是一个一层又一层的结构.

5.3 静态-MWT

线性索引的一种优化, 将索引本身构建成一棵树, 将数据构成一个个的子节点, 其中某一些
子节点加上唯一的父节点, 就是线性索引中的某一个块数据集合.

这样子就能更加快速的找到索引(而并非顺序查找), 你看, 很多知识点都是一步步累积的提出,
并非一蹴而就的.

5.4 静态-倒排

上述所有索引都是(key, value)的结构, 但是倒排索引却是将某一个value作为键值, 实现
这样的效果: (value, key), 类似 SQL 中Where命令效果:

1
select id, nickname from account where nickname like '%bamboo%';

这样就能快速的基于属性进行检索, 得到所有主键值(id).

倒排索引的存储代价太大, 如果数据的重复度不高的, value又很长的化, 相当于存储两倍的
(len(value) + len(id))的空间, 另外维护工作量也过于巨大.

5.5 动态-B-树

B-树(平衡多路查找树)的提出, 主要用以确保在外存索引结构中树的平衡性, 从而减少外存访问开销. 保证查找数据、顺序访问、插入数据及删除的动作,都在对数时间内完成.

简单定义如下, 对于m阶的B-树, 其中 M 表示分叉:

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

search-btree1

详细信息见B-tree

5.6 动态-红黑树

红黑树(二叉查找树), 在二叉查找树的基础上增加了着色和相关性质, 使得红黑树相对平衡,
确保红黑树的查找, 插入, 删除的时间复杂度最坏为O(logn).

红黑树的定义如下, 对于有n个结点的红黑树, 其高度使用在logn下:

  • 每一个结点要么红, 要么黑
  • 根节点是黑的
  • 每一个叶节点是黑的
  • 如果一个节点是红的, 那么他们的子节点是黑的
  • 对于任意结点, 其到叶子结点的每一条路径都包含相同的黑结点

rbtree

详细信息见rbtree.