? 静态索引结构
动态索引结构
散列
可扩充散列静态索引结构
示例,有一个存放职工信息的数据表,每一个职工对象有近 1k 字节的信息,正好占据一个页块的存储空间 。
当数据对象个数 n 很大时,如果用无序表形式的静态搜索结构存储,采用顺序搜索,则搜索效率极低。如果采用有序表存储形式的静态搜索结构,则插入新记录进行排序,时间开销也很可观。这时可采用索引方法来实现存储和搜索。
线性索引 (Linear Index List)
100
140
180
220
260
300
340
380
key addr
03 180
08 140
17 340
24 260
47 300
51 380
83 100
95 220
职工号 姓名 性别 职务 婚否
83 张珊 女 教师 已婚 …
08 李斯 男 教师 已婚,..
03 王鲁 男 教务员 已婚,..
95 刘琪 女 实验员 未婚,..
24 岳跋 男 教师 已婚,..
47 周斌 男 教师 已婚,..
17 胡江 男 实验员 未婚,..
51 林青 女 教师 未婚,..
索引表 数据表
假设内存工作区仅能容纳 64k 字节的数据,
在某一时刻内存最多可容纳 64 个对象以供搜索。
如果对象总数有 14400 个,不可能把所有对象的数据一次都读入内存。无论是顺序搜索或折半搜索,都需要多次读取外存记录。
如果在索引表中每一个索引项占 4个字节,每个索引项索引一个职工对象,则 14400 个索引项需要 56.25k 字节,在内存中可以容纳所有的索引项 。
这样只需从外存中把索引表读入内存,经过搜索索引后确定了职工对象的存储地址,再经过 1 次读取对象操作就可以完成搜索 。
稠密索引,一个索引项对应数据表中一个对象的索引结构 。 当对象在外存中 按加入顺序存放而不是按关键码有序存放 时必须采用 稠密索引 结构,这时的索引结构叫做索引非顺序结构 。
稀疏索引,当对象在外存中有序存放时,可以把所有 n 个对象分为 b 个子表 (块 )存放,
一个索引项对应数据表中一组对象 (子表 )。
在子表中,所有对象 可能按关键码有序地存放,也可能无序地存放 。 但所有这些子表 必须分块有序,后一个子表中所有对象的关键码均大于前一个子表中所有对象的关键码 。
它们都存放在数据区中。
另外建立一个索引表。索引表中每一表目叫做 索引项,它记录了子表中 最大关键码 max
_key以及该子表 在数据区中的起始位臵 obj _
addr。
第 i 个索引项是第 i 个子表的索引项,i = 0,
1,…,n-1。 这样的索引结构叫做 索引顺序结构 。
对索引顺序结构进行搜索时，一般分为两级搜索,
先在 索引表 ID 中搜索给定值 K,确定满足
ID[i-1].max_key < K? ID[i].max_key
22 12 13 30 29 33
36 42 44 48 39 40
60 74 56 79 80 66
92 82 88 98 94
子表 1
子表 2
子表 3
子表 4
数据区
33
48
80
98
索引表
1
2
3
4
max_ max_
key addr
的 i 值,即待查对象可能在的子表的序号 。
然后再在第 i 个子表中按给定值搜索要求的对象 。
索引表是按 max_key有序的,且长度也不大,
可以折半搜索,也可以顺序搜索 。
各子表内各个对象如果也按对象关键码有序,
可以采用折半搜索或顺序搜索 ; 如果不是按对象关键码有序,只能顺序搜索 。
索引顺序搜索的搜索成功时的平均搜索长度
ASLIndexSeq = ASLIndex + ASLSubList
其中,ASLIndex 是在索引表中搜索子表位臵的平均搜索长度,ASLSubList 是在子表内搜索对象位臵的搜索成功的平均搜索长度 。
设把长度为 n 的表分成均等的 b 个子表,每个子表 s 个对象,则 b =?n/s?。 又设表中每个对象的搜索概率相等,则每个子表的搜索概率为 1/b,子表内各对象的搜索概率为 1/s。
若对 索引表 和 子表 都用 顺序搜索,则索引顺序搜索的搜索成功时的平均搜索长度为
ASLIndexSeq = (b+1)/2+(s+1)/2 = (b+s)/2 +1
索引顺序搜索的平均搜索长度与 表中的对象个数 n 有关，与 每个子表中的对象个数 s 有关。在给定 n 的情况下,s 应选择多大？
用数学方法可导出,当 s = 时,ASLIndexSeq
取极小值 +1。这个值比顺序搜索强，但比折半搜索差。但如果子表存放在外存时，
还要受到页块大小的制约。
若采用折半搜索确定对象所在的子表,则搜索成功时的平均搜索长度为
ASLIndexSeq = ASLIndex + ASLSubList
log2 (b+1)-1 + (s+1)/2
log2(1+n / s ) + s/2
n
n
倒排表 (Inverted Index List)
对包含有大量数据对象的数据表或文件进行搜索时，最常用的是针对对象的 主关键码 建立索引。 主关键码可以唯一地标识该对象 。
用主关键码建立的索引叫做主索引 。
主索引的每个索引项给出对象的关键码和对象在表或文件中的存放地址 。
但在实际应用中有时需要针对其它属性进行搜索。例如，查询如下的职工信息：
(1) 列出所有教师的名单；
对象关键码 key 对象存放地址 addr
(2) 已婚的女性职工有哪些人？
这些信息在数据表或文件中都存在，但都不是关键码，为回答以上问题，只能到表或文件中去顺序搜索，搜索效率极低。
因此，除主关键码外，可以 把一些经常搜索的属性设定为次关键码,并 针对每一个作为次关键码的属性,建立次索引 。
在次索引中，列出该属性的所有取值，并对每一个取值建立有序链表，把所有具有相同属性值的对象按存放地址递增的顺序或按主关键码递增的顺序链接在一起。
次索引的索引项由 次关键码,链表长度 和 链表本身 等三部分组成。
例如，为了回答上述的查询，我们可以分别建立“性别”、“婚否”和“职务”次索引。
性别次索引次关键码 男 女计 数 5 3
地址指针指针 03 08 17 24 47 51 83 95
婚否次索引次关键码 已婚 未婚计 数 5 3
地址指针指针 03 08 24 47 83 17 51 95
职务次索引次关键码 教师 教务员 实验员计 数 5 1 2
地址指针指针 08 24 47 51 83 03 17 95
(1) 列出所有教师的名单；
(2) 已婚的女性职工有哪些人？
通过顺序访问,职务,次索引中的,教师,
链，可以回答上面的查询 (1)。
通过对,性别,和,婚否,次索引中的,女性,链和,已婚,链进行求“交”运算，就能够找到所有既是女性又已婚的职工对象，
从而回答上面的查询 (2)。
倒排表是次索引的一种实现 。在表中所有次关键码的链都保存在次索引中，仅通过搜索次索引就能找到所有具有相同属性值的对象。
在次索引中 记录对象存放位臵的指针 可以用主关键码表示,可通过搜索次索引确定该对象的主关键码,再通过搜索主索引确定对象的存放地址 。
在倒排表中各个属性链表的长度大小不一,
管理比较困难。为此引入单元式倒排表。
在单元式倒排表中,索引项中不存放 对象的存储地址,存放 该对象所在硬件区域的标识 。
硬件区域可以是磁盘柱面、磁道或一个页块,以 一次 I / O 操作能存取的存储空间作为硬件区域 为最好。
为使索引空间最小,在索引中标识这个硬件区域时可以使用一个能转换成地址的二进制数,整个次索引形成一个 (二进制数的 ) 位矩阵 。
例如,对于记录学生信息的文件,次索引可以是如图所示的结构。二进位的值为 1 的硬件区域包含具有该次关键码的对象。
如果在硬件区域 1,…… 中有要求的对象。
然后将硬件区域 1,…… 等读入内存，在其中进行检索，确定就可取出所需对象。
硬 件 区 域
1 2 3 4 5 … 251 252 253 254 …
次关键码 1 男 1 0 1 1 1 … 1 0 1 1 …
( 性别 ) 女 1 1 1 1 1 … 0 1 1 0 …
次关键码 2 广东 1 0 0 1 0 … 0 1 0 0 …
( 籍贯 ) 北京 1 1 1 1 1 … 0 0 1 1 …
上海 0 0 1 1 1 … 1 1 0 0 …
……
次关键码 3 建筑 1 1 0 0 1 … 0 1 0 1 …
( 专业 ) 计算机 0 0 1 1 1 … 0 0 1 1 …
电机 1 0 1 1 0 … 1 0 1 0 …
……
单元式倒排表结构
m 路静态搜索树
当数据对象数目特别大，索引表本身也很大，
在内存中放不下，需要分批多次读取外存才能把索引表搜索一遍。
此时,可以建立索引的索引 (二级索引 )。二级索引可以常驻内存，二级索引中一个索引项对应一个索引块，登记该索引块的最大关键码及该索引块的存储地址。
1 0 1 1 1 …… 1 0 1 1
1 0 0 1 0 …… 0 1 0 0
A N D 1 1 0 0 1 …… 0 1 0 1
1 0 0 0 0 …… 0 0 0 0
如果二级索引在内存中也放不下，需要分为许多块多次从外存读入。可以建立二级索引的索引 (三级索引 )。这时，访问外存次数等于读入索引次数再加上 1次读取对象。
02 06 11 15 18 23 29 32 38 41 45 49 52 60 77 95
(06,) (15,) (23,) (32,) (41,) (49,) (60,) (95,)
(23,) (41,) (95,)
root
head
必要时,还可以有 4级索引,5极索引,… 。
这种多级索引结构形成一种 m 叉树。树中每一个分支结点表示一个索引块,它 最多存放 m 个索引项,每个索引项分别给出各子树结点 (低一级索引块 ) 的最大关键码和结点地址。
树的叶结点中各索引项给出在数据表中存放的对象的关键码和存放地址。这种 m叉树用来作为多级索引，就是 m路搜索树。
m路搜索树 可能是 静态索引结构,即结构在初始创建，数据装入时就已经定型，在整个运行期间，树的结构不发生变化。
多级索引结构形成 m 路搜索树
m路搜索树 还可能是 动态索引结构,即在整个系统运行期间,树的结构随数据的增删及时调整,以保持最佳的搜索效率。
数据区一级索引二级索引三级索引四级索引动态搜索结构
现在我们所讨论的 m 路搜索树多为可以动态调整的多路搜索树,它的一般定义为：
一棵 m 路搜索树,它或者是一棵空树,或者是满足如下性质的树：
根最多有 m 棵子树,并具有如下的结构：
n,P0,( K1,P1 ),( K2,P2 ),……,( Kn,Pn )
其中,Pi 是指向子树的指针,0? i? n < m; Ki
是关键码,1? i? n < m。 Ki < Ki+1,1? i < n。
动态的 m 路搜索树
在子树 Pi 中所有的关键码都 小于 Ki+1,且大于 Ki,0 < i < n。
在子树 Pn 中所有的关键码都 大于 Kn；
在子树 P0 中的所有关键码都 小于 K1。
子树 Pi 也是 m 路搜索树,0? i? n。
一棵 3路搜索树的示例
35
20 40a
b c d
e
25 3010 15 45 50
m 路搜索树的类定义
template <class Type> class Mtree { //基类
public:
Triple<Type> & Search ( const Type & );
protected:
Mnode<Type> root;
int m;
}
AVL树是 2路搜索树。如果已知 m 路搜索树的度 m 和它的 高度 h,则树中的 最大结点数 为
1
1
1 1
0
h
h
i
i m
m
m
(等比级数前 h 项求和 )
每个结点中 最多有 m-1 个关键码,在一棵高度为 h 的 m 路搜索树中关键码的最大个数为 mh+1-1。
高度 h=2 的二叉树,关键码最大个数为 7；
高度 h=3 的 3路搜索树,关键码最大个数为 34-1 = 80。
struct Triple {
Mnode<Type> * r; //结点地址指针
int i; int tag; //结点中关键码序号 i
}; //tag=0,搜索成功 ； tag=1,搜索不成功标识 m 路搜索树搜索结果的三元组表示
m 路搜索树上的搜索算法
在 m 路搜索树上的搜索过程是一个 在结点内搜索 和 自根结点向下逐个结点搜索 的交替的过程。
35
20 40a
b c d
e
25 3010 15 45 50
root
搜索 35
template <class Type> Triple<Type> &
Mtree<Type>,,Search ( const Type& x ) {
Triple result; //记录搜索结果三元组
GetNode ( root ); //读入根结点
Mnode <Type> *p = root,*q = NULL;
while ( p != NULL ) { //从根开始检测
int i = 0; p->key[(p->n)+1] = MAXKEY;
while ( p->key[i+1] < x ) i++; //结点内搜索
if ( p->key[i+1] == x ) { //搜索成功
result.r = p; result.i = i+1; result.tag = 0;
return result;
}
q = p; p = p->ptr[i]; //向下一层结点搜索
GetNode (p); //读入该结点
}
result.r = q; result.i = i; result.tag = 1;
return result; //搜索失败,返回插入位置
}
提高搜索树的路数 m,可以改善树的搜索性能 。 对于给定的关键码数 n,如果搜索树是平衡的,可以使 m 路搜索树的性能接近最佳 。 下面将讨论一种称之为 B 树的平衡的 m
路搜索树 。
B 树
一棵 m 阶 B 树是一棵平衡的 m 路搜索树,它或者是空树,或者是满足下列性质的树：
根结点至少有 2 个子女。
除根结点以外的所有结点 (不包括失败结点 )至少有?m/2?个子女。
所有的失败结点都位于同一层。
在 B 树中的“失败”结点是当搜索值 x不在树中时才能到达的结点。
事实上，在 B 树的每个结点中还包含有一组指针 D[m]，指向实际对象的存放地址。
30
K[i]与 D[i] (1? i? n < m) 形成一个 索引项
(K[i],D[i])，通过 K[i]可找到某个对象的存储地址 D[i]。
一棵 B 树是平衡的 m 路搜索树，但一棵平衡的 m 路搜索树不一定是 B 树。
35
20 40
25 3010 15 45 50
root
45 5035
4020
root
10 15 25
非 B 树 B 树
B 树的类定义和 B 树结点类定义
template <class Type> class Btree,
public Mtree<Type> {
//继承 m 路搜索树的所有属性和操作
public:
int Insert ( const Type& x );
int Remove ( const Type& x );
};
template <class Type> class Mnode {
// B 树结点类定义
private:
int n; //结点中关键码个数
Mnode<Type> *parent; //双亲指针
Type key[m+1]; //关键码数组 1?m-1
Mnode<Type> *ptr[m+1]; //子树指针数组
};
B 树的搜索算法
B 树的搜索算法继承了 m 路搜索树 Mtree上的搜索算法 。
B 树的搜索过程是一个在结点内搜索和循某一条路径向下一层搜索交替进行的过程 。
B 树的搜索时间与 B 树的阶数 m 和 B 树的高度 h直接有关,必须加以权衡 。
在 B 树上进行搜索,搜索成功所需的时间取决于关键码所在的层次 ; 搜索不成功所需的时间取决于树的高度 。
如果定义 B 树的高度 h 为失败结点所在的层次,需要了解树的高度 h 与树中的关键码个数 N 之间的关系 。
如果让 B 树每层结点个数达到最大,且设 关键码总数 为 N,则树的高度达到最小：
h =?logm( N*(m-2)/(m-1)+1)?-1
设在 m 阶 B 树中每层结点个数达到最少,则
B 树的高度可能达到最大。设树中关键码个数为 N，从 B 树的定义知：
0层 1 个结点
1层 至少 2 个结点
2层 至少 2?m / 2?个结点
3层 至少 2?m / 2? 2 个结点
如此类推,
h-1 层 至少有 2?m / 2? h-2 个结点。所有这些结点都不是失败结点。
高度 h与关键码个数 N之间的关系
若树中关键码有 N个,则失败结点数为 N+1。
这是因为失败数据一般与已有关键码交错排列。因此，有
N +1 = 失败结点数 = 位于第 h 层的结点数
2?m / 2? h-1
N? 2?m / 2? h-1-1
h-1? log?m / 2? ( (N +1) / 2 )
所有的非失败结点所在层次为 0? h-1。
示例：若 B 树的阶数 m = 199,关键码总数 N
= 1999999，则 B 树的高度 h 不超过
log100 1000000 +1= 4
m值的选择
如果提高 B 树的阶数 m,可以减少树的高度,
从而减少读入结点的次数,因而可减少读磁盘的次数。
事实上,m受到内存可使用空间的限制 。
当 m 很大超出内存工作区容量时,结点不能一次读入到内存,增加了读盘次数,也增加了结点内搜索的难度。
m值的选择,应使得在 B 树中找到关键码 x
的时间总量达到最小 。
这个时间由两部分组成：
从磁盘中读入结点所用时间
在结点中搜索 x 所用时间
根据定义,B 树的每个结点的大小都是固定的,结点内有 m-1 个索引项 (Ki,Di,Pi),1? i
< m。其中,Ki 所占字节数为?,Di 和 Pi 所占字节数为?，则 结点大小近似为 m(?+2?)
个字节 。读入一个结点所用时间为：
tseek + tlatency + m(? + 2?) ttran = a + bm
B 树的插入
B 树是从空树起,逐个插入关键码而生成的。
在 B 树，每个非失败结点的关键码个数都在
[?m/2?-1,m-1]
之间。
插入在 某个叶结点 开始。如果在关键码插入后结点中的 关键码个数超出了上界 m-1，则结点需要“分裂”，否则可以直接插入 。
实现结点“分裂”的原则是：
设结点 p 中已经有 m-1 个关键码，当再插入一个关键码后结点中的状态为
( m,P0,K1,P1,K2,P2,……,Km,Pm)
其中 Ki < Ki+1,1? i < m
这时必须把结点 p 分裂成两个结点 p 和 q，
它们包含的信息分别为：
结点 p：
(?m/2?-1,P0,K1,P1,……,K?m/2?-1,P?m/2?-1)
结点 q：
(m-?m/2?,P?m/2?,K?m/2?+1,P?m/2?+1,……,Km,Pm)
位于中间的关键码 K?m/2?与指向新结点 q 的指针形成一个二元组 ( K?m/2?,q )，插入到这两个结点的双亲结点中去。
结点“分裂”的示例
2 53 75
n P0 K1 P1 K2 P2
p
3 53 75 139
n P0 K1 P1 K2 P2 K3 P3
p
加入 139,
结点溢出
1 75
n P0 K1 P1
1 53
n P0 K1 P1
1 139
n P0 K1 P1
结点分裂
P q
49 75
示例,从空树开始加入关键码建立 3阶 B 树
n=1 加入 53
53
n=2 加入 75
53 75
n=3 加入 139
75
13953
n=5 加入 49,145
75
139 14549 53
n=6 加入 36
139 1455336
在插入新关键码时，需要自底向上分裂结点，最坏情况下从被插关键码所在叶结点到根的路径上的所有结点都要分裂。
若设 B 树的高度为 h,那么在 自顶向下 搜索到 叶结点 的过程中需要进行
h 次读盘。
n=7 加入 101
49
5336
139
145101
75
B 树的插入算法
template <class Type> int Btree<Type>,,
Insert ( const Type & x ) {
Triple<Type> loc = Search (x); //找 x的位置
if ( !loc.tag ) return 0; //找到,不再插入
Mnode<Type> *p = loc.r,*q; //未找到,插入
Mnode<Type> *ap = NULL,*t;
Type K = x; int j = loc.i; //插入位置 p,j
while (1) {
if ( p->n < m-1) { //当前结点未满
insertkey ( p,j,K,ap ); //(K,ap)插入 j后
PutNode (p); return 1; //写出
} //结点已满,分裂
int s = (m+1)/2; //求?m/2?
insertkey ( p,j,K,ap ); //(K,ap)插入 j后
q = new Mnode<Type>; //建立新结点
move ( p,q,s,m ); //从 p向 q 搬送
K = p->key[s]; ap = q; //分界码上移
if ( p->parent != NULL ) { //双亲不是根
t = p->parent; GetNode (t); //读入双亲
j = 0; t->key[(t->n)+1] = MAXKEY;
while ( t->key[j+1] < K ) j++; //找插入点
q->parent = p->parent;
PutNode (p); PutNode (q);
p = t;
} //继续 while(1) 循环,向上调整
else { //双亲是根
root = new Mnode<Type>; //创建新根
root->n = 1; root->parent = NULL;
root->key[1] = K; root->ptr[0] = p;
root->ptr[1] = ap;
q->parent = p->parent = root;
PutNode (p); PutNode (q);
PutNode (root); return 1; //跳出返回
}
}
}
当分裂一个非根的结点时需要向磁盘写出 2
个结点,当分裂根结点时需要写出 3 个结点。
如果我们所用的内存工作区足够大,使得在向下搜索时,读入的结点在插入后向上分裂时不必再从磁盘读入,那么,在完成一次插入操作时 需要读写磁盘的次数 =
= 找插入结点向下读盘次数 +
+ 分裂非根结点时写盘次数 +
+ 分裂根结点时写盘次数 =
= h+2(h-1)+3 =
= 3h+1。
B 树的删除
在 B 树上删除一个关键码时,首先需要找到这个关键码所在的结点,从中删去这个关键码。若该结点不是叶结点,且被删关键码为
Ki,1? i? n,则在删去该关键码之后,应以该结点 Pi 所指示子树中的最小关键码 x 来代替被删关键码 Ki 所在的位臵,然后在 x 所在的叶结点中删除 x。
在叶结点上的删除有 4 种情况。
① 被删关键码所在叶结点同时又是根结点且删除前该结点中关键码个数 n? 2，则直接删去该关键码并将修改后的结点写回磁盘。
② 被删关键码所在叶结点不是根结点且删除前该结点中关键码个数 nm/2?,则直接删去该关键码并将修改后的结点写回磁盘,删除结束。
③ 被删关键码所在叶结点删除前关键码个数 n
=?m/2?-1,若这时与该结点相邻的右兄弟
(或左兄弟 )结点的关键码个数 nm/2?，则可按以下步骤调整该结点、右兄弟 (或左兄弟 ) 结点以及其双亲结点，以达到新的平衡。
36 49m = 3 删除 36 49
55 58
删除 55简单删除
75 80
m = 3
删除 55
10 40 65
60 7030
50a
cb
d e f g h
58 75 8010 40 65
60 7030
50a
cb
d e f g h
将双亲结点中刚刚大于 (或小于 ) 该被删关键码的关键码 Ki (1? i? n) 下移；
将右兄弟 (或左兄弟 ) 结点中的最小 (或最大 )关键码上移到双亲结点的 Ki 位臵；
将右兄弟 (或左兄弟 ) 结点中的最左 (或最右 ) 子树指针平移到被删关键码所在结点中最后 (或最前 ) 子树指针位臵；
在右兄弟 (或左兄弟 ) 结点中，将被移走的关键码和指针位臵用剩余的关键码和指针填补、调整。再将结点中的关键码个数减
1。
结点联合调整
55 58 75 80
m = 3 删除 65
10 40 65
60 7030
50a
cb
d e f g h
55 58 8010 40 70
60 7530
50a
cb
d e f g h
调整 g,c,h
删除 65
70
删除 70
55 58 80
m = 3 删除 70
10 40
60 7530
50a
cb
d e f g h
55 8010 40 60
58 7530
50a
cb
d e f g h
调整 f,c,g
结点联合调整
④ 被删关键码所在叶结点删除前关键码个数
n =?m/2?-1,若这时与该结点相邻的右兄弟
(或左兄弟 )结点的关键码个数 n =?m/2?-1,
则必须按以下步骤合并这两个结点。
将双亲结点 p 中相应关键码下移到选定保留的结点中。若要合并 p 中的子树指针 Pi
与 Pi+1 所指的结点,且保留 Pi 所指结点,则把 p 中的关键码 Ki+1下移到 Pi 所指的结点中。
把 p 中子树指针 Pi+1 所指结点中的全部指针和关键码都照搬到 Pi 所指结点的后面。删去 Pi+1 所指的结点。
在结点 p 中用后面剩余的关键码和指针填补关键码 Ki+1 和指针 Pi+1。
修改结点 p 和选定保留结点的关键码个数。
在合并结点的过程中,双亲结点中的关键码个数减少了。
若双亲结点是根结点且结点关键码个数减到
0,则将该双亲结点删去,合并后保留的结点成为新的根结点 ; 否则将双亲结点与合并后保留的结点都写回磁盘,删除处理结束。
若双亲结点不是根结点且关键码个数减到
m/2?-2，又要与它自己的兄弟结点合并,重复上面的合并步骤。最坏情况下这种结点合并处理要自下向上直到根结点。
55
删除 55结点合并
80
m = 3 删除 55
10 40 60
58 7530
50a
cb
d e f g h
合并 f,g
58 60 8010 40
7530
50a
cb
d e f h
8055
删除 80结点合并
m = 3 删除 80
10 40 60
58 7530
50a
cb
d e f g h
合并 g,h
60 755510 40
5830
50a
cb
d e f h
55
非叶结点删除删除 50
删除 55
55 58 75 80
m = 3 删除 50
10 40 65
60 7030
50a
cb
d e f g h
58 75 80
删除 55
10 40 65
60 7030
a
cb
d e f g h
用 55取代用 58取代
58
75 8010 40 65
60 7030
a
cb
d e f g h
合并 f,g
58
75 8010 40 60 65
7030
a
cb
d e f h
结点合并与调整删除 70
58
8010 40 60 65
7530
a
cb
d e f h
删除 70
用 75取代删除 75
58
10 40 60 65
8030
a
cb
d e f h
删除 75
用 80取代调整 f,c,h
58
8010 40 60
6530
a
cb
d e f h
删除 10
8030 40 60f h
58 65
d
b
B 树的关键码删除算法
template <class Type> int Btree<Type>,:
Delete ( const Type & x ) {
Triple<Type> loc = Search (x); //搜索 x
if ( loc.tag ) return 0; //未找到,不删除
Mnode<Type> *p = loc.r,*q,*s; //找到,删除
int j = loc.i;
if ( p->ptr[j] != NULL ) { //非叶结点
s = p->ptr[j]; GetNode (s); q = p;
while ( s != NULL ) { q = s; s = s->ptr[0]; }
p->key[j] = q->key[1]; //从叶结点替补
compress ( q,1 ); //在叶结点删除
p = q; //转化为叶结点的删除
}
else compress ( p,j ); //叶结点,直接删除
int d = (m+1)/2; //求?m/2?
while (1) { //调整或合并
if ( p->n < d -1 ) { //小于最小限制
j = 0; q = p->parent; //找到双亲
GetNode (q);
while ( j <= q->n && q->ptr[j] != p )
j++;
if ( !j ) LeftAdjust ( p,q,d,j ); //调整
else RightAdjust ( p,q,d,j );
p = q; //向上调整
if ( p == root ) break;
}
else break;
}
if ( !root->n ) { //调整后根的 n减到 0
p = root->ptr[0];
delete root; root = p; //删根
root->parent = NULL; //新根
}
}
B+树
一棵 m 阶 B+树可以定义如下：
树中每个非叶结点 最多有 m 棵子树 ；
根结点 (非叶结点 )至少有 2 棵子树 。 除根结点外,其它的非叶结点至少有?m/2? 棵子树 ; 有 n 棵子树的非叶结点有 n-1 个关键码 。
所有叶结点都处于同一层次上,包含了全部关键码及指向相应数据对象存放地址的指针,且叶结点本身按关键码从小到大顺序链接；
叶结点的子树棵数 n 可以多于 m,可以少于 m,视关键码字节数及对象地址指针字节数而定。若设结点可容纳最大关键码数为 m1,则指向对象的地址指针也有 m1 个。
10 15 18 20 22 23 31 33 45 48 52
18 23
33
33
叶结点中的子树棵数 n 应满足
n? [?m1/2?,m1]。
若根结点同时又是叶结点,则结点格式同叶结点。
所有的非叶结点可以看成是索引部分,结点中关键码 Ki 与指向子树的指针 Pi 构成对子树 (即下一层索引块 )的索引项 ( Ki,Pi )，
Ki 是子树中最小的关键码。
特别地,子树指针 P0 所指子树上所有关键码均小于 K1。结点格式同 B 树。
叶结点中存放的是对实际数据对象的索引。
在 B+树中有两个头指针,一个指向 B+ 树的根结点，一个指向关键码最小的叶结点。
可对 B+树进行两种搜索运算：
循叶结点链 顺序搜索
另一种是从根结点开始,进行自顶向下,
直至叶结点的 随机搜索 。
在 B+树上进行随机搜索、插入和删除的过程基本上与 B 树类似。只是在搜索过程中，
如果非叶结点上的关键码等于给定值，搜索并不停止，而是继续沿右指针向下，一直查到叶结点上的这个关键码。
B+树的搜索分析类似于 B 树。
B+树的插入仅在叶结点上进行 。 每插入一个 (关键码 -指针 )索引项后都要判断结点中的子树棵数是否超出范围。
当插入后结点中的子树棵数 n > m1 时,需要将叶结点分裂为两个结点,它们的关键码分别为?(m1+1)/2?和?(m1+1)/2?。
它们的双亲结点中应同时包含这两个结点的最小关键码和结点地址。此后,问题归于在非叶结点中的插入了。
3个关键码的 B+树
10 12 23
加入关键码 33,结点分裂
10 12 23 33
23
10 12 18 20 22 23 33
18 23
加入更多的关键码
在非叶结点中关键码的插入与叶结点的插入类似,但非叶结点中的子树棵数的上限为
m,超出这个范围就需要进行结点分裂。
在做根结点分裂时,因为没有双亲结点,就必须创建新的双亲结点,作为树的新根。这样树的高度就增加一层了。
B+树的删除仅在叶结点上进行 。当在叶结点上删除一个 (关键码 -指针 )索引项后,结点中的子树棵数仍然不少于?m1/2?，这属于简单删除,其上层索引可以不改变。
如果删除的关键码是该结点的最小关键码,
但因在其上层的副本只是起了一个引导搜索的“分界关键码”的作用,所以上层的副本仍然可以保留。
如果在叶结点中删除一个 (关键码 -指针 )索引项后，该结点中的子树棵数 n 小于结点子树棵数的下限?m1/2?，必须做结点的调整或合并工作。
删除 18
10 15 18 20 22 23 31 33 45 48 52
18 23
33
33
10 15 20 22 23 31 33 45 48 52
18 23
33
33
删除关键码 18上层索引不改
10 15 18 20 22 23 31 33 45 48 52
18 23
33
33
15 18 20 22 23 31 33 45 48 52
20 23
33
33
删除关键码 10,18移入结点,索引改 20
删除 10
如果右兄弟结点的子树棵数已达到下限
m1/2?,没有多余的关键码可以移入被删关键码所在的结点,必须进行两个结点的合并 。 将右兄弟结点中的所有 (关键码 -指针 )
索引项移入被删关键码所在结点,再将右兄弟结点删去 。
结点的合并将导致双亲结点中,分界关键码,的减少,有可能减到非叶结点中子树棵数的下限?m/2? 以下 。 这样将引起非叶结点的调整或合并 。 如果根结点的最后两个子女结点合并,树的层数就会减少一层 。
10 15 18 20 22 23 31 33 45 48 52
18 23
33
33
15 18 20 22 23 31
20 23 45
删除关键码 33,右边两结点合并,影响到非叶结点合并,可能直到根结点,导致高度减少删除 33
45 48 52
散列 (Hashing)
在计算科学中把词典当作一种抽象数据类型。
在讨论词典抽象数据类型时，把词典定义为
<名字 -属性 >对的集合。
在现实中,经常遇到按给定的值进行查询的事例。为此,必须在开发相应软件时考虑在记录的存放位臵和用以标识它的数据项 (称为关键码 )之间的对应关系,从而选择适当的数据结构,很方便地根据记录的关键码检索到对应记录的信息。
词典 (Dictionary)的抽象数据类型
根据问题的不同,可以为名字和属性赋予不同的含义。
例如,在图书馆检索目录中,名字是书名,属性是索书号及作者等信息 ; 在计算机活动文件表中,名字是文件名,属性是文件地址、
大小等信息。
词典的抽象数据类型
const int DefaultSize = 26;
template<class Name,class Attribute>
class Dictionary {
public:
Dictionary ( int size = DefaultSize );
int IsIn ( Name name );
Attribute * Find ( Name name );
void Insert ( Name name,Attribute attr );
void Remove ( Name name );
}
在词典的所有操作中，最基本的只有 3 种：
Find (搜索 ),Insert (插入 ),Remove (删除 )。
在选择词典的表示时，必须确保这几个操作的实现。
通常，用 文件 (表格 ) 来表示实际的对象集合,
用 文件记录 (表格的表项 )来表示单个对象。
这样,词典中的 <名字 -属性 >对 将被存于 记录
(表项 )中，通过表项的 关键码 ( <名字 -属性
>对 的名字 ) 来标识该表项。
表项的存放位臵及其关键码之间的对应关系可以用一个二元组表示：
( 关键码 key，表项位臵指针 addr )
这个二元组构成搜索某一指定表项的索引项。
考虑到搜索效率,可以用顺序表方式、二叉搜索树或多路搜索树方式组织词典。本节讨论另一种组织词典的方法,即散列表结构。
静态散列方法
散列方法在 表项存储位臵 与 其关键码 之间建立一个 确定的对应函数关系 Hash( )，使每个关键码与结构中一个唯一存储位臵相对应：
Address ＝ Hash ( Rec.key )
在搜索时,先对表项的关键码进行函数计算,
把函数值当做表项的存储位臵,在结构中按此位臵取表项比较。若关键码相等,则搜索成功。在存放表项时,依相同函数计算存储位臵,并按此位臵存放。这种方法就是散列方法。
在散列方法中使用的转换函数叫做 散列函数 。
按此方法构造出来的表或结构就叫做 散列表 。
使用散列方法进行搜索不必进行多次关键码的比较,搜索速度比较快,可以直接到达或逼近具有此关键码的表项的实际存放地址。
散列函数是一个压缩映象函数 。关键码集合比散列表地址集合大得多。因此有可能经过散列函数的计算，把不同的关键码映射到同一个散列地址上，这就产生了 冲突 。
示例：有一组表项，其关键码分别是
12361,07251,03309,30976
采用的散列函数是
hash(x) = x % 73 + 13420
其中，,%” 是除法取余操作。
则有,hash(12361) = hash(07250) = hash(03309)
= hash(30976) = 13444。 就是说,对不同的关键码,通过散列函数的计算,得到了同一散列地址。 我们称这些产生冲突的散列地址相同的不同关键码为 同义词 。
由于关键码集合比地址集合大得多,冲突很难避免。 所以对于散列方法,需要讨论以下两个问题：
构造散列函数时的几点要求：
散列函数应是简单的，能在较短的时间内计算出结果。
散列函数的定义域必须包括需要存储的全部关键码,如果散列表允许有 m 个地址时,其值域必须在 0 到 m-1 之间。
散列函数
对于给定的一个关键码集合,选择一个计算简单且地址分布比较均匀的散列函数,避免或尽量减少冲突；
拟订解决冲突的方案。
① 直接定址法此类函数取关键码的某个线性函数值作为散列地址：
Hash ( key ) ＝ a * key + b { a,b为常数 }
这类散列函数是一对一的映射，一般不会产生冲突。但是，它要求散列地址空间的大小与关键码集合的大小相同。
散列函数计算出来的 地址应能均匀分布在整个地址空间中,若 key 是从关键码集合中随机抽取的一个关键码,散列函数应能以同等概率取 0 到 m-1 中的每一个值。
示例：有一组关键码如下,{ 942148,941269,
940527,941630,941805,941558,942047,
940001 }。 散列函数为
Hash (key) = key - 940000
Hash (942148) = 2148 Hash (941269) = 1269
Hash (940527) = 527 Hash (941630) = 1630
Hash (941805) = 1805 Hash (941558) = 1558
Hash (942047) = 2047 Hash (940001) = 1
可以按计算出的地址存放记录。
② 数字分析法
设有 n 个 d 位数,每一位可能有 r 种不同的符号。这 r 种不同的符号在各位上出现的频率不一定相同。 可根据散列表的大小,选取其中各种符号分布均匀的若干位作为散列地址。
计算各位数字中符号分布均匀度? k 的公式,
其中,表示第 i 个符号在第 k 位上出现的次数,n/r 表示各种符号在 n 个数中均匀出现的期望值。计算出的? k 值越小，表明在该位 (第 k 位 ) 各种符号分布得越均匀。
r
i
k
ik rn
1
2)/(αλ
kiα
9 4 2 1 4 8 ① 位,? 1 = 57.60
9 4 1 2 6 9 ② 位,? 2 = 57.60
9 4 0 5 2 7 ③ 位,? 3 = 17.60
9 4 1 6 3 0 ④ 位,? 4 = 5.60
9 4 1 8 0 5 ⑤ 位,? 5 = 5.60
9 4 1 5 5 8 ⑥ 位,? 6 = 5.60
9 4 2 0 4 7
9 4 0 0 0 1
① ② ③ ④ ⑤ ⑥
若散列表地址范围有 3 位数字,取各关键码的 ④⑤⑥ 位做为记录的散列地址。也可以把第①，②,③ 和第⑤位相加,舍去进位位,变成一位数,与第④,⑥ 位合起来作为散列地址。
数字分析法仅适用于事先明确知道表中所有关键码每一位数值的分布情况，它完全依赖于关键码集合。如果换一个关键码集合，选择哪几位要重新决定。
③ 除留余数法
设散列表中允许地址数为 m,取一个不大于
m,但最接近于或等于 m 的质数 p 作为除数,
利用以下函数把关键码转换成散列地址：
hash ( key ) = key % p p? m
其中,“%” 是整数除法取余的运算，要求这时的质数 p 不是接近 2的幂。
示例,有一个关键码 key = 962148,散列表大小 m = 25,即 HT[25]。取质数 p= 23。散列函数 hash ( key ) = key % p。则散列地址为
hash ( 962148 ) = 962148 % 23 = 12。
可以按计算出的地址存放记录。需要注意的是,使用上面的散列函数计算出来的地址范围是 0到 22,因此,从 23到 24这几个散列地址实际上在一开始是不可能用散列函数计算出来的,只可能在处理溢出时达到这些地址。
④ 平方取中法
此方法在词典处理中使用十分广泛。
它先计算构成关键码的标识符的内码的平方,
然后按照散列表的大小取中间的若干位作为散列地址 。
设标识符可以用一个计算机字长的内码表示 。
因为内码平方数的中间几位一般是由标识符所有字符决定,所以对不同的标识符计算出的散列地址大多不相同,即使其中有些字符相同 。
在平方取中法中,一般取散列地址为 2 的某次幂 。 例如,若散列地址总数取为 m = 2r,则对内码的平方数取中间的 r 位 。 如果 r = 3，
所取得的散列地址参看图的最右一列 。
标识符 内码 内码的平方 散列地址
A 01 01 001
A1 0134 20420 042
A9 0144 23420 342
B 02 4 004
DMAX 04150130 21526443617100 443
DMAX1 0415013034 5264473522151420 352
AMAX 01150130 135423617100 236
AMAX1 0115013034 3454246522151420 652
标识符的八进制内码表示及其平方值
⑤ 折叠法
此方法把关键码自左到右分成 位数相等 的几部分,每一部分的位数应与散列表地址位数相同,只有最后一部分的位数可以短一些。
把这些部分的数据叠加起来,就可以得到具有该关键码的记录的散列地址。
有两种叠加方法：
移位法 —把各部分的最后一位对齐相加；
分界法 —各部分不折断,沿各部分的分界来回折叠,然后对齐相加,将相加的结果当做散列地址。
示例,设给定的关键码为 key = 23938587841,
若 存储空间限定 3 位,则划分结果为每段 3
位,上述关键码可划分为 4段：
239 385 878 41
把超出地址位数的最高位删去,仅保留最低的 3位，做为可用的散列地址。
移位法分界法
一般当关键码的位数很多,而且关键码每一位上数字的分布大致比较均匀时,可用这种方法得到散列地址 。
以上介绍了几种常用的散列函数 。 在实际工作中应根据关键码的特点,选用适当的方法 。 有人曾用,轮盘赌,的统计分析方法对它们进行了模拟分析,结论是平方取中法最接近于,随机化,。
处理冲突的闭散列方法因为任一种散列函数也不能避免产生冲突，
因此选择好的解决冲突的方法十分重要。
为了减少冲突，对散列表加以改造。若设散列表 HT 有 m 个地址,将其改为 m 个桶 。其桶号与散列地址一一对应,第 i (0? i < m) 个桶的桶号即为第 i 个散列地址。
每个桶可存放 s 个表项,这些表项的关键码互为同义词。如果对两个不同表项的关键码用散列函数计算得到同一个散列地址，就产生了冲突，它们可以放在同一个桶内的不同位臵。
只有当桶内所有 s 个表项位臵都放满表项后再加入表项才会产生溢出 。
通常桶的大小 s 取的比较小,因此在桶内大多采用顺序搜索。
闭散列也叫做开地址法。在闭散列情形,所有的桶都直接放在散列表数组中 。 因此每个桶只有一个表项 ( s = 1 )。
若设散列表中各桶的编址为 0 到 m-1,当要加入一个表项 R2时,用它的关键码 R2.key,
通过散列函数 hash ( R2.key ) 的计算，得到它的存放桶号 j。
但在存放时发现此桶已被另一个表项 R1 占据,
发生了冲突,必须处理冲突。为此,需把 R2 存放到表中“下一个”空桶中。 如果表未被装满,则在允许的范围内必定还有空桶。
(1) 线性探查法 (Linear Probing)
假设给出一组表项，它们的关键码为 Burke,
Ekers,Broad,Blum,Attlee,Alton,Hecht,
Ederly。采用的散列函数是：取其第一个字母在字母表中的位臵。
Hash (x) = ord (x) - ord (?A?)
//ord ( ) 是求字符内码的函数
可得 Hash (Burke) = 1 Hash (Ekers) = 4
Hash (Broad) = 1 Hash (Blum) = 1
Hash (Attlee) = 0 Hash (Hecht) = 7
Hash (Alton) = 0 Hash (Ederly) = 4
设散列表 HT[26],m = 26。采用 线性探查法处理冲突,则散列结果如图所示。
0 1 2 3 4
Attlee Burke Broad Blum Ekers
Alton Ederly Hecht
5 6 7 8 9
(1) (1) (2) (3) (1)
(6) (3) (1)
需要搜索或加入一个表项时,使用散列函数计算桶号：
H0 = hash ( key )
一旦发生冲突，在表中顺次向后寻找,下一个”空桶 Hi 的递推公式为：
Hi = ( Hi-1 +1 ) % m,i =1,2,…,m-1
即用以下的线性探查序列在表中寻找,下一个”空桶 的桶号：
H0 +1,H0 +2,…,m-1,0,1,2,…,H0-1
亦可写成如下的通项公式：
Hi = ( H0 + i ) % m,i =1,2,…,m-1
当发生冲突时,探查下一个桶。当循环 m-1
次后就会回到开始探查时的位臵,说明待查关键码不在表内,而且表已满,不能再插入新关键码。
用 平均搜索长度 ASL (Averagy Search Length)
衡量散列方法的搜索性能。
根据搜索成功与否，它又有 搜索成功的平均搜索长度 ASLsucc和 搜索不成功的平均搜索长度 ASLunsucc之分。
搜索成功的平均搜索长度 ASLsucc 是指 搜索到表中已有表项的平均探查次数 。它是找到表中各个已有表项的探查次数的平均值。
搜索不成功的平均搜索长度 ASLunsucc 是指在表中搜索不到待查的表项，但找到插入位臵的平均探查次数 。它是表中所有可能散列到的位臵上要插入新元素时为找到空桶的探查次数的平均值。
在使用线性探查法对示例进行搜索时,搜索成功的平均搜索长度为：
搜索不成功的平均搜索长度为,
8
1
.
8
181)361321(1
8
1
8
1
i
CiA S L s u c c
.266226 1823456789A S L u n s u c c
下面是用 线性探查法 在散列表 ht 中搜索给定值 x 的算法。如果查到某一个 j，使得
ht[j].info == Active && ht[j].Element == x
则搜索成功；否则搜索失败。造成失败的原因可能是表已满，或者是原来有此表项但已被删去，或者是无此表项且找到空桶。
class HashTable {
//用线性探查法处理冲突时散列表类的定义
public:
enum KindOfEntry { Active,Empty,Deleted };
HashTable ( ),TableSize ( DefaultSize )
{ AllocateHt ( ); CurrentSize = 0; }
~HashTable ( ) { delete [ ] ht; } //析构函数
const HashTable & operator = //表复制
( const HashTable & ht2 );
int Find ( const Type& x ); //搜索
int Insert ( const Type& x ); //插入
int Remove ( const Type& x ); //删除
int IsIn ( const Type& x ) //判存在
{ return ( i = Find (x) ) >= 0? 1,0; }
void MakeEmpty ( ); //置空
private:
struct HashEntry { //散列表表项
Type Element; //表项关键码
KindOfEntry info; //三种状态
int operator== ( HashEntry& ); //判相等
int operator!= ( HashEntry & ); //判不等
HashEntry ( ),info (Empty ) { } //构造函数
HashEntry (const Type& E,KindOfEntry
i = Empty ),Element (E),info (i) { }
};
enum { DefualtSize = 11 }
HashEntry *ht; //散列表数组
int CurrentSize,TableSize; //当前及最大桶数
void AllocateHt ( ) //分配空间
{ ht = new HashEntry[TableSize ]; }
int FindPos ( const Type & x ) const;
} //散列函数
template <class Type> int HashTable <Type>::
Find ( const Type& x ) {
//线性探查法的搜索算法,函数返回找到位置 。
//若返回负数可能是空位,若为 -TableSize则失败 。
int i = FindPos ( x ),j = i; //计算散列地址
while ( ht[j].info != Empty &&
ht[j].Element != x ){
j = ( j + 1 ) % TableSize; //冲突,找空桶
if ( j == i ) return -TableSize; //失败,表满
}
if ( ht[j].info == Active ) return j; //成功
else -j; //失败
}
在利用散列表进行各种处理之前,必须首先将散列表中原有的内容清掉 。 只需将表中所有表项的 info域臵为 Empty即可 。
散列表存放的表项不应有重复的关键码 。 在插入新表项时,如果发现表中已经有关键码相同的表项,则不再插入 。
在闭散列情形下不能真正删除表中已有表项 。
删除表项会影响其他表项的搜索 。 若把关键码为 Broad的表项真正删除,把它所在位臵的
info域臵为 Empty,以后在搜索关键码为 Blum
和 Alton的表项时就查不下去,会错误地判断表中没有关键码为 Blum和 Alton的表项 。
若想删除一个表项,只能给它做一个删除标记 deleted进行逻辑删除,不能把它真正删去。
逻辑删除的副作用 是：在执行多次删除后,
表面上看起来散列表很满,实际上有许多位臵没有利用。
template <class Type>
void HashTabe<Type>,,MakeEmpty ( ) {
//置表中所有表项为空
for ( int i = 0; i < TableSize; i++)
ht[i].info = Empty;
CurrentSize = 0;
}
template <class Type>
const HashTable <Type>& HashTable<Type>,:
operator = ( const HashTable<Type>& ht2 ) {
//重载函数：从散列表 ht2 复制到当前散列表
if ( this != &ht2 ) {
delete [ ] ht;
TableSize = ht2.TableSize; AllocateHt ( );
for ( int i = 0; i < TableSize; i++ )
ht[i] = ht2.ht[i];
CurrentSize = ht2.CurrentSize;
}
return *this;
}
template <class Type> int HashTable<Type>::
Insert ( const Type & x ) {
//将新表项 x 插入到当前的散列表中
if ( ( int i = Find (x) ) >= 0 ) return 0; //不插入
else if ( i != -TableSize &&
ht[-i].info != Active ) { //在 -i 处插入 x
ht[-i].Element = x;
ht[-i].info = Active;
CurrentSize++;
return 1;
}
else return 0;
}
template <class Type> int HashTable <Type>,,
Remove ( const Type& x ) {
//在当前散列表中删除表项 x
if ( ( int i = Find (x) ) >= 0 ) { //找到,删除
ht[i].info = deleted; //做删除标记
CurrentSize--;
return 1;
}
else return 0;
}
线性探查方法容易产生,堆积,,不同探查序列的关键码占据可用的空桶,为寻找某一关键码需要经历不同的探查序列,导致搜索时间增加。
算法分析
设散列表的 装填因子 为? = n / (s*m),其中
n 是表中已有的表项个数,s 是每个桶中最多可容纳表项个数,m是表中的桶数 。
可用? 表明散列表的装满程度 。 越大,表中表项数越多,表装得越满,发生冲突可能性越大 。
通过对线性探查法的分析可知,为搜索一个关键码所需进行的探查次数的期望值 P 大约是 (2-?)/(2-2?)。 虽然平均探查次数较小,
但在最坏情况下的探查次数会相当大 。
(2) 二次探查法 (quadratic probing)
为改善“堆积”问题,减少为完成搜索所需的平均探查次数,可使用二次探查法。
通过某一个散列函数对表项的关键码 x 进行计算,得到桶号,它是一个非负整数。
H0 = hash(x)
二次探查法在表中寻找“下一个”空桶的公式：
Hi = (H0 + i 2 ) % m,
Hi = (H0 - i 2 ) % m,i = 1,2,…,( m-1)/2
式中的 m 是表的大小，它应是一个值为
4k+3 的质数，其中 k 是一个整数。 如 3,7,
11,19,23,31,43,59,127,251,503,… 。
探查序列如 H0,H0+1,H0-1,H0+4,H0-4,… 。
在做 (H0- i2 ) % m 的运算时,当 H0- i2 < 0 时,
运算结果也是负数 。 实际算式可改为
j = (H0- i2 ) % m,if ( j < 0 ) j += m
示例：给出一组关键码 { Burke,Ekers,
Broad,Blum,Attlee,Alton,Hecht,Ederly }。
散列函数为,Hash (x)＝ ord (x)－ ord ('A')
用它计算可得
Hash (Burke) = 1 Hash (Ekers) = 4
Hash (Broad) = 1 Hash (Blum) = 1
Hash (Attlee) = 0 Hash (Hecht) = 7
Hash (Alton) = 0 Hash (Ederly) = 4
因为可能桶号是 0? 25,取满足 4k+3 的质数，
表的长度为 TableSize = 31，利用二次探查法得到的散列结果如图所示。
0 1 2 3 4 5
Blum Burke Broad Ekers Ederly
Hecht
6 7 8 9 10 11
Alton Attlee
(3) (1) (2) (1) (2)
(1)
25 26 27 28 29 30
(5) (3)
利用二次探查法处理溢出
使用 二次探查法 处理冲突时的 搜索成功的平均搜索长度 为：
搜索不成功的平均搜索长度 为：
.8183)512121(38181
8
1
i
CiA S L s u c c
26
402 0)22325(6
26
1A S L u n s u c c
设散列表桶数为 m,待查关键码为 x,第一次通过散列函数计算出的桶号为 H0=hash(x)。当发生冲突时，第 i-1 次和第 i 次计算出来的
“下 一个”桶号分别为：
,% ) 1)( (
,% ) 1)( (
2
0
( 1 )
1
2
0
( 0 )
1
miHH
miHH
i
i
,% ) (
,% ) (
2
0
( 1 )
2
0
( 0 )
miHH
miHH
i
i
相减，可以得到：
,% ) 1*2 (
,% ) 1*2 (
( 1 )
1
( 1 )
( 0 )
1
( 0 )
miHH
miHH
ii
ii
从而
,% ) 1*2 (
,% ) 1*2 (
( 1 )
1
( 1 )
( 0 )
1
( 0 )
miHH
miHH
ii
ii
只要知道上一次的桶号 和,当 i 增加 1
时可以从 和 简单地导出 和,
不需要每次计算 i 的平方 。
在冲突处理算法 Find 中,首先求出 H0作为当前桶号 CurrentPos,当发生冲突时求,下一个,桶号,i = 1。
此时用一个标志 odd 控制是加 i2 还是减 i2 。
若 odd == 0 加 i 2,并臵 odd = 1；
若 odd == 1 减 i 2,并臵 odd = 0。
下次 i 进一后,又可由 odd 控制先加后减 。
处理冲突的算法
(0)1?iH (1)1?iH
(0)1?iH (1)1?iH (1)iH(1)iH
template <class Type> int HashTable<Type>,:
Find ( const Type& x ) {
int i = 0,odd = 0;
int CurrentPos = HashPos ( x ); //初始 桶号
while ( ht[CurrentPos].info != Empty &&
ht[CurrentPos].Element != x ) { //冲突
if ( !odd ) { // odd == 0 加 i 2
CurrentPos = ( CurrentPos + 2* i-1) %
TableSize;
odd = 1;
}
else { // odd == 1 减 i 2
CurrentPos = ( CurrentPos-2*i+1 ) %
TableSize;
odd = 0;
}
}
LastFindOK = ht[CurrentPos].info == Active;
return CurrentPos;
}
可以证明,当 表的长度 TableSize为质数 且 表的装填因子?不超过 0.5 时,新的表项 x 一定能够插入,且任何一个位臵不会被探查两次。，
只要表中至少有一半空，就不会有表满问题。
在搜索时可以不考虑表满的情况 ; 但在插入时 必须确保表的装填因子?不超过 0.5。 如果超出,必须将表长度扩充一倍,进行表的分裂 。
在删除一个表项时,为确保搜索链不致中断,
也只能做表项的逻辑删除,即将被删表项的标记 info改为 Deleted。
(3) 双散列法
使用双散列方法时,需要两个散列函数 。
第一个散列函数 Hash( ) 按表项的关键码
key 计算表项所在的桶号 H0 = Hash(key)。
一旦冲突,利用第二个散列函数 ReHash( )
计算该表项到达,下一个,桶的移位量 。 它的取值与 key 的值有关,要求它的取值应是小于地址空间大小 TableSize,且与
TableSize 互质的正整数 。
若设表的长度为 m = TableSize,则在表中寻找,下一个,桶的公式为：
j = H0 = Hash(key),p = ReHash(key)；
j = ( j + p ) % m；
p是小于 m且与 m互质的整数
利用双散列法,按一定的距离,跳跃式地寻找
“下一个”桶,减少了“堆积”的机会。
双散列法的探查序列也可写成：
Hi = (H0 + i * ReHash(key) ) % m，
i =1,2,…,m-1
最多经过 m-1次探查,它会遍历表中所有位臵,回到 H0 位臵。
示例：给出一组表项关键码 { 22,41,53,46,
30,13,01,67 }。散列函数为：
Hash(x)＝ (3x) % 11。
散列表为 HT[0..10],m = 11。因此，再散列函数为 ReHash(x) = (7x) % 10 +1。
Hi = ( Hi-1 + (7x) % 10 +1 ) % 11,i = 1,2,?
H0(22) = 0 H0(41) = 2 H0(53) = 5
H0(46) = 6 H0(30) = 2 冲突 H1 = (2+1) = 3
H0(13) = 6 冲突 H1 = (6+2) = 8
H0(01) = 3 冲突 H1 = (3+8) = 0 冲突 H2 =
(0+8) = 8 冲突 H3 = (8+8) = 5 冲突 H4 =
(5+8) = 2 冲突 H5 = (2+8) = 10
H0(67) = 3 冲突 H1 = (3+10) = 2 冲突 H2 =
(2+10) = 1
22 67 41 30 53 46 13 01
(1) (3) (1) (2) (1) (1) (2) (6)
0 1 2 3 4 5 6 7 8 9 10
1 8 2 5 3 4 6 7
搜索成功的平均搜索长度
搜索不成功的平均搜索长度
每一散列位臵的移位量有 10种,1,2,?,
10。先计算每一散列位臵各种移位量情形下找到下一个空位的比较次数,求出平均值；
再计算各个位臵的平均比较次数的总平均值。
22 67 41 30 53 46 13 01
(1) (3) (1) (2) (1) (1) (2) (6)
0 1 2 3 4 5 6 7 8 9 10
8
176)211213(1
8
1A S L s u c c
Rehash( )的取法很多 。 例如,当 m是质数时,
可定义
ReHash(key) = key % (m-2) +1
ReHash(key) =?key / m? % (m-2)+1
当 m 是 2 的方幂时,ReHash(key) 可取从 0
到 m-1 中的任意一个奇数。
处理冲突的开散列方法 — 链地址法
开散列方法首先对关键码集合用某一个散列函数计算它们的存放位臵 。
若设散列表地址空间的所有位臵是从 0 到
m-1,则关键码集合中的所有关键码被划分为 m个子集,具有相同地址的关键码归于同一子集 。 我们称同一子集中的关键码互为同义词 。 每一个子集称为一个桶 。
通常各个桶中的表项通过一个单链表链接起来,称之为同义词子表 。 所有桶号相同的表项都链接在同一个同义词子表中,各链表的表头结点组成一个向量 。
向量的元素个数与桶数一致。桶号为 i 的同义词子表的表头结点是向量中的第 i 个元素。
示例：给出一组表项关键码 { Burke,Ekers,
Broad,Blum,Attlee,Alton,Hecht,Ederly }。
散列函数为,Hash (x)＝ ord (x)－ ord ('A')。
用它计算可得：
Hash (Burke) = 1 Hash (Ekers) = 4
Hash (Broad) = 1 Hash (Blum) = 1
Hash (Attlee) = 0 Hash (Hecht) = 7
Hash (Alton) = 0 Hash (Ederly) = 4
散列表为 HT[0..25],m = 26。
0
1
2
3
4
5
6
7
8
9
Attlee Alton
Burke Broad Blum
Ekers Ederly
Ekers 8
13
8
1*33*24*1
s u c cA S L
26
34
18)*12
113114(3
26
1
u n s u c cA S L
通常,每个桶中的同义词子表都很短,设有
n 个关键码通过某一个散列函数,存放到散列表中的 m 个桶中 。 那么每一个桶中的同义词子表的平均长度为 n / m。 以搜索平均长度为 n / m 的同义词子表代替了搜索长度为 n
的顺序表,搜索速度快得多 。
利用链地址法处理溢出时的类定义
template <class Type> class ListNode { //链结点
friend HashTable;
private:
Type key; //关键码
ListNode *link; //链指针
};
typedef ListNode<Type> *ListPtr;
class HashTable { //散列表的类定义
public:
HashTable( int size = defaultsize ) //构造函数
{ buckets = size; ht = new ListPtr[buckets]; }
private:
int buckets; //桶数
ListPtr <Type> *ht; //散列表数组的头指针
};
循链搜索的算法
template<class Type>
Type * HashTable<Type>:,
Find ( const Type & x,) {
int j = HashFunc ( x,buckets ); //初始桶号
ListPtr<Type> * p = ht[j]; //桶地址
while ( p != NULL )
if ( p->key == x ) return & p->key;
else p = p->link;
return 0;
}
其它如插入,删除操作可参照单链表的插入,
删除等算法来实现 。
应用开散列法处理冲突,需要增设链接指针,
似乎增加了存储开销 。 事实上,由于闭散列法必须保持大量的空闲空间以确保搜索效率,
如二次探查法要求装填因子 0.5,而表项所占空间又比指针大得多,所以使用开散列法反而比闭散列法节省存储空间 。
散列表分析
散列表是一种直接计算记录存放地址的方法,
它在关键码与存储位臵之间直接建立了映象 。
当选择的散列函数能够得到均匀的地址分布时,在搜索过程中可以不做多次探查。
由于很难避免冲突,增加了搜索时间。 冲突的出现,与 散列函数的选取 (地址分布是否均匀 ),处理冲突的方法 (是否产生堆积 ) 有关。
在实际应用中使用关键码进行散列时,如在用作关键码的许多标识符具有相同的前缀或后缀,或者是 相同字符的不同排列 的场合，
不同的散列函数往往导致散列表具有不同的搜索性能 。
下图给出一些实验结果。
= n / m 0,5 0 0,7 5 0,9 0 0,9 5
散列函数种类开散列法闭散列法开散列法闭散列法开散列法闭散列法开散列法闭散列法平平 方方 取取 中中 11,,22 66 11,,77 33 11,,44 00 99,,77 55 11,,44 55 33 11 00,,11 44 11,,44 77 33 11 00,,55 33
除留余数 1,1 9 4,5 2 1,3 1 1 0,2 0 1,3 8 2 2,4 2 1,4 1 2 5,7 9
移位折叠 1,3 3 2 1,7 5 1,4 8 6 5,1 0 1,4 0 7 1 0,0 1 1,5 1 1 1 8,5 7
分界折叠 1,3 9 2 2,9 7 1,5 7 4 8,7 0 1,5 5 6 9,6 3 1,5 1 9 1 0,5 6
数字分析 1,3 5 4,5 5 1,4 9 3 0,6 2 1,5 2 8 9,2 0 1,5 2 1 2 5,5 9
理论值 1,2 5 1,5 0 1,3 7 2,5 0 1,4 5 5,5 0 1,4 8 1 0,5 0
搜索关键码时所需对桶的平均访问次数从图中可以看出,开散列法优于闭散列法 ；
在散列函数中,用除留余数法作散列函数优于其它类型的散列函数,最差的是折叠法。
当装填因子?较高时,选择的散列函数不同,散列表的搜索性能差别很大。在一般情况下多选用除留余数法,其中的除数在实用上应选择不含有 20以下的质因数的质数。
对散列表技术进行的实验评估表明,它 具有很好的平均性能,优于一些传统的技术,如平衡树 。但散列表 在最坏情况下性能很不好 。
如果对一 个有 n 个关键码的散列表执行一次搜索或插入操作，最坏情况下需要 O(n)
的时间。
Knuth对不同的冲突处理方法进行了概率分析。
若设? 是散列表的装填因子：
用地址分布均匀的散列函数 Hash( )计算桶号。
Sn 是搜索一个随机选择的关键码 xi (1? i? n)
所需的关键码比较次数的期望值
Un 是在长度为 m 的散列表中 n 个桶已装入表项的情况下，装入第 n+1 项所需执行的关键码比较次数期望值 。
前者称为在? = n / m 时的搜索成功的平均搜索长度，后者称为在?= n / m时的搜索不成功的平均搜索长度。
m
n
表中预设的最大记录数表中已装有记录数?
用不同的方法溢出处理冲突时散列表的平均搜索长度如图所示。
平 均 搜 索 长 度 ASL
处 理 冲 突的 方 法搜索成功
Sn
搜索不成功 Un
( 登入新记录 )
闭散线性探查法
)(
列法伪随机探查法二次探查法双散列法
1l o g
1
e
开 散 列 法
( 同义词子表法 )
e
散列表的装填因子? 表明了表中的装满程度 。 越大,说明表越满,再插入新元素时发生冲突的可能性就越大 。
散列表的搜索性能,即 平均搜索长度 依赖于散列表的装填因子,不直接依赖于 n 或 m。
不论表的长度有多大,我们总能选择一个合适的装填因子,以把平均搜索长度限制在一定范围内 。
例 求散列表大小并设计散列函数
设有一个含 200个表项的散列表，用二次探查法解决冲突，按关键码查询时找到一个新表项插入位臵的平均探查次数不超过 1.5，则散列表项应能够至少容纳多少个表项。再设计散列函数 （设搜索不成功的平均搜索长度为
Un＝ 1 / (1 -α),其中 α为装填因子）
解答：设表中表项个数 n = 200，搜索不成功的平均搜索长度
Un＝ 1 / (1 -α)? 1.5 1/3
n / m = 200 / m = 1/3 m? 600
可扩充散列
可扩充散列是一种动态散列方法，它对传统的散列技术进行了扩充，使之能够动态地适应对文件存储容量的需求，并能保持高效的搜索效率。
二叉 Trie树
若设每一个关键码由 2个字符组成,而每一个字符用 3 个二进位表示。则有标识符 A0 A1 B0 B1 C0 C1 C2 C3
二进位 100 100 101 101 110 110 110 110
表示 000 001 000 001 000 001 010 011
假设把这些关键码放到有 4 个页块 的文件中,
每页最多可以容纳 2 个关键码,各页可通过
2 个二进位 00,01,10,11 加以索引。现在利用各关键码的最低 2 位来决定它应放到哪个页块上。
A0,B0 C2 C3
0
0 1 0 1
1
基于 4个页块的 2层索引
A1,B1
一般地,根据各关键码的二进位表示,从最低位到最高位进行划分,各页块的索引构成一个二叉树结构 。这就是 二叉 Trie树 。
首先,在根结点处按各关键码的最低位是 1
还是 0,划分为两组。 对于每一组再按次低位是 1 还是 0 继续分组,如此分下去,直到每组剩下不多于 2 个关键码为止。
因此，在二叉 Trie树中有两类结点,分支结点 和 叶结点 。 分支结点 按其相关二进位是 1
还是 0,分为两个方向 ; 仅在 叶结点 包含指向关键码存放页块的指针 。
A0,B0 C2 C3
0
0 1 0 1
1
A1,B1 C5
0 1
插入新的关键码 C5 时,因为 C5 的二进制表示 110101的最低两位二进位是 01,所以应把它放到 A1,B1所在的 第 3页中。但是此时该页块已满,发生了溢出。为此,将 第 3页 扩充一倍，一页分裂为两页。
再插入一个新关键码 C1,它应插入到 A1,B1
所在的页块中。这时又发生溢出,需要再分裂 A1,B1 所在页块：根据 A1,B1,C1 的最低 4 位将它们重新分配到这两个页块中。
A0,B0 C2 C3
0
0 1 0 1
1
C5
0 1
B1
0 1
A1,C1
以上两个插入结果降低了树搜索效率 。 为解决上述问题,1979年 Fagin等人提出了可扩充散列方法 。
该方法采用一种特殊的散列函数,把关键码转换成二进制数字表示的伪随机数集合,取其最低若干位作为页块地址,从而避免了关键码的不均匀分布 。 并且把 二叉 Trie树映射为目录表,以避开在二叉 Trie树中的长时间搜索过程 。
利用可扩充散列技术组织的文件叫做散列文件。
若设有 n 个记录,每个记录有一个关键码域用以唯一标识这个记录。又设每个页块有 p 个记录,整个文件有 m 个页块,则散列文件的存储利用率可用 n/(m*p) 来度量。
从上面的例子可知，存在着两个问题：
对某个页块的访问时间取决于区分关键码所需的二进位数。
如果关键码的分布不均匀，最后产生的二叉 Trie树是倾斜的。
将二叉 Trie树转换为目录表
为将二叉 Trie树转换为目录表,首先需要将二叉 Trie树的分支结点部分 (索引部分 ) 转换为一棵满二叉树 ——即所有指向叶结点的分支结点都位于同一层次上。然后 再把这棵二叉树映射为指示各个页块的目录表 。
一般地,目录表由一组指向页块的指针组成 。 如果区分所有的关键码需要 k 位二进制数,则 目录项个数应为 2k,其编址为 0 到
2k -1。
A0,B0 C2 C3
0
0 1 0 1
1
A1,B1 C5
0 1 0 10 1 0 1
A0,B0 C2 C5A1,B1 C3
000 001 010 011 100 101 110 111目录满二叉树 反向读页地址正向读页地址
一般使用 关键码的最后 k 个二进位 作为 目录项下标 来搜寻该关键码所在页块的指针,
然后对这个页块进行搜索。
A0,B0 C2A1,B1 C3
00 01 10 11
上面的目录由 4 个目录项组成,其编址从 0
到 3。 通过目录项的指针,可找到相应页块的地址,从而读取该页块的内容 。
目录或页块的 可区分编址位数 叫做其 深度 。
在目录表中插入一个新关键码后,其深度可能增加 1。为了保持最高搜索效率,需要压缩目录的深度,使其深度仍为 2。
由于有 5 个目录项,需要由最低 3 位来区分它们,为此，设臵 8个目录项，其下标从 0到 7。
这样，某些页块就有多个指针指向它。
C5C3
000 001 010 011 100 101 110 111
A0,B0 A1,B1 C2
使用目录表来表示一棵二叉 Trie树,允许关键码序列动态地增长和收缩 。
这里假设操作系统能够有效地为人们提供页块,并能够回收页块到可利用空间中去。
访问一个页块的步骤为：
利用散列函数找到目录项的地址；
按此地址检索相关的页块。
如果所有的关键码在各个页块中的分配不均衡,则目录表可能会增长得相当大,且多数指针指到同一个页块。为防止出现此种情况,
使用一个均匀分布的散列函数得到一个随机地址，用它作为二进位下标。
可扩充散列结构 由一组页块和一个目录表构成 。每一个页块包括的信息有
该页块的局部深度 PgDepth,它指明该页块中存放的对象的二进位地址的低位部分有多少位是相同的；
该页块关键码个数 Count和 存放关键码的数组 Names。页块都存储在文件中。
目录表由目录项组成。每个目录项是一个指示某一页块的地址的指针。一般用一个数组 Directory来存放它们，其下标范围从
0 到 MaxDir-1。 目录表深度为 DicDepth,
它指明为区分各个页块所需的二进位数 。
插入 C5,分裂 01
页,目录扩一倍
A0,B0 C2A1,B1 C3
00 01 10 11
DirDepth=2
PgDepth PgDepth PgDepth PgDepth
=2 =2 =2 =2
C5C3
000 001 010 011 100 101 110 111
A0,B0 A1,B1
DirDepth
=2
C2
PgDepth PgDepth PgDepth PgDepth PgDepth
=2 =3 =2 =2 =3
关键码插入及页块分裂
在向一个页块插入关键码 key 时,如果该页块不满,可以直接将关键码插入 ; 如果该页块已满,需要分裂页块。
若原来页块的 PgDepth=d,分裂后两个伙伴页块的二进制地址都增加一位,它们的局部深度 PgDepth=d+1。除了低阶共享的 d位外,
用最高阶的一位来区分它们。
在页块分裂后必须扩充目录表。让目录表的深度加 1，所有的目录项增加一倍,原来地址为的目录项中的页块指针分别放到 0和
1的两个目录项中。
C5
C3
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
B1
C2
A0,B0
A1,C1
DirDepth=4
PgDepth=2
PgDepth=4
PgDepth=2
PgDepth=2
PgDepth=3
PgDepth=4
如果目录项的二进制地址有 d 位,则整个目录表的深度 DicDepth = d,目录项个数 (表的长度 )有 2d 个。
DicDepth = log2(目录表中目录项个数 ) = 目录表的二进位数 。
有时有多个指针指向同一个页块,它表明该页块的局部深度小于目录表深度,
PgDepth < DicDepth
如果页块的 PgDepth = d'，则目录表中同时指向该页块的指针个数必为 2d-d'。
初始时 DicDepth=0,目录项个数 n = 2DicDepth
= 1,所有关键码都在同一个页块上。
关键码删除及页块合并
在执行关键码删除时,若 两个伙伴页块中的关键码个数总和少于或等于其中一个单独页块的容量时,就应把这两个页块合并成一个。
求二进制地址为 p 的某目录项所指页块的伙伴页块的方法：
若设目录项 p 所指页块的 PgDepth=d',把地址 p 的第 d' 位求反,得到一个新的二进制地址 p',地址为 p' 的目录项所指页块即为原页块的伙伴 页块。
页块中关键码减少可能会导致目录表的紧缩。
合并伙伴页块的工作包括：
将关键码合并到其中任一个页块中；
释放空闲的页块；
将原来的指针都指向合并后的页块。
如果目录中指向每一个页块的指针个数都大于或等于 2,即所有页块的 PgDepth < DicDepth
需要紧缩目录。其过程与目录扩充的过程相反。
性能分析
可扩充散列技术是一种非常好的问题解决方法,其 散列文件的地址空间可以扩充和收缩,
文件自身能够增长和缩小 。
在时间方面,用基于目录表的可扩充散列方法进行检索,仅需要 2次磁盘访问 。因为不存在溢出问题,访问时间与文件大小无关,时间开销达到 O(1)。
在空间方面,因增加不均匀分布的关键码可能会导致目录表扩充一倍，许多指针指到同一页块，这样会消耗许多存储空间。
在空间利用率方面评价散列技术的方式仍然用装载因子 α来衡量,
Fagin,Nievergelt等人做了一系列的试验和模拟。他们发现,可扩充散列的页块空间利用率在 0.53 到 0,94 之间周期性地变动。若给定的记录数为 r,一个页块可容纳 b 个记录,
则所需的平均页块数 N 和装载因子? 为：
表中最大可容纳记录 数表中已存储的记录数α?
Nb
r
2b
rN
ln?
动态索引结构
散列
可扩充散列静态索引结构
示例,有一个存放职工信息的数据表,每一个职工对象有近 1k 字节的信息,正好占据一个页块的存储空间 。
当数据对象个数 n 很大时,如果用无序表形式的静态搜索结构存储,采用顺序搜索,则搜索效率极低。如果采用有序表存储形式的静态搜索结构,则插入新记录进行排序,时间开销也很可观。这时可采用索引方法来实现存储和搜索。
线性索引 (Linear Index List)
100
140
180
220
260
300
340
380
key addr
03 180
08 140
17 340
24 260
47 300
51 380
83 100
95 220
职工号 姓名 性别 职务 婚否
83 张珊 女 教师 已婚 …
08 李斯 男 教师 已婚,..
03 王鲁 男 教务员 已婚,..
95 刘琪 女 实验员 未婚,..
24 岳跋 男 教师 已婚,..
47 周斌 男 教师 已婚,..
17 胡江 男 实验员 未婚,..
51 林青 女 教师 未婚,..
索引表 数据表
假设内存工作区仅能容纳 64k 字节的数据,
在某一时刻内存最多可容纳 64 个对象以供搜索。
如果对象总数有 14400 个,不可能把所有对象的数据一次都读入内存。无论是顺序搜索或折半搜索,都需要多次读取外存记录。
如果在索引表中每一个索引项占 4个字节,每个索引项索引一个职工对象,则 14400 个索引项需要 56.25k 字节,在内存中可以容纳所有的索引项 。
这样只需从外存中把索引表读入内存,经过搜索索引后确定了职工对象的存储地址,再经过 1 次读取对象操作就可以完成搜索 。
稠密索引,一个索引项对应数据表中一个对象的索引结构 。 当对象在外存中 按加入顺序存放而不是按关键码有序存放 时必须采用 稠密索引 结构,这时的索引结构叫做索引非顺序结构 。
稀疏索引,当对象在外存中有序存放时,可以把所有 n 个对象分为 b 个子表 (块 )存放,
一个索引项对应数据表中一组对象 (子表 )。
在子表中,所有对象 可能按关键码有序地存放,也可能无序地存放 。 但所有这些子表 必须分块有序,后一个子表中所有对象的关键码均大于前一个子表中所有对象的关键码 。
它们都存放在数据区中。
另外建立一个索引表。索引表中每一表目叫做 索引项,它记录了子表中 最大关键码 max
_key以及该子表 在数据区中的起始位臵 obj _
addr。
第 i 个索引项是第 i 个子表的索引项,i = 0,
1,…,n-1。 这样的索引结构叫做 索引顺序结构 。
对索引顺序结构进行搜索时，一般分为两级搜索,
先在 索引表 ID 中搜索给定值 K,确定满足
ID[i-1].max_key < K? ID[i].max_key
22 12 13 30 29 33
36 42 44 48 39 40
60 74 56 79 80 66
92 82 88 98 94
子表 1
子表 2
子表 3
子表 4
数据区
33
48
80
98
索引表
1
2
3
4
max_ max_
key addr
的 i 值,即待查对象可能在的子表的序号 。
然后再在第 i 个子表中按给定值搜索要求的对象 。
索引表是按 max_key有序的,且长度也不大,
可以折半搜索,也可以顺序搜索 。
各子表内各个对象如果也按对象关键码有序,
可以采用折半搜索或顺序搜索 ; 如果不是按对象关键码有序,只能顺序搜索 。
索引顺序搜索的搜索成功时的平均搜索长度
ASLIndexSeq = ASLIndex + ASLSubList
其中,ASLIndex 是在索引表中搜索子表位臵的平均搜索长度,ASLSubList 是在子表内搜索对象位臵的搜索成功的平均搜索长度 。
设把长度为 n 的表分成均等的 b 个子表,每个子表 s 个对象,则 b =?n/s?。 又设表中每个对象的搜索概率相等,则每个子表的搜索概率为 1/b,子表内各对象的搜索概率为 1/s。
若对 索引表 和 子表 都用 顺序搜索,则索引顺序搜索的搜索成功时的平均搜索长度为
ASLIndexSeq = (b+1)/2+(s+1)/2 = (b+s)/2 +1
索引顺序搜索的平均搜索长度与 表中的对象个数 n 有关，与 每个子表中的对象个数 s 有关。在给定 n 的情况下,s 应选择多大？
用数学方法可导出,当 s = 时,ASLIndexSeq
取极小值 +1。这个值比顺序搜索强，但比折半搜索差。但如果子表存放在外存时，
还要受到页块大小的制约。
若采用折半搜索确定对象所在的子表,则搜索成功时的平均搜索长度为
ASLIndexSeq = ASLIndex + ASLSubList
log2 (b+1)-1 + (s+1)/2
log2(1+n / s ) + s/2
n
n
倒排表 (Inverted Index List)
对包含有大量数据对象的数据表或文件进行搜索时，最常用的是针对对象的 主关键码 建立索引。 主关键码可以唯一地标识该对象 。
用主关键码建立的索引叫做主索引 。
主索引的每个索引项给出对象的关键码和对象在表或文件中的存放地址 。
但在实际应用中有时需要针对其它属性进行搜索。例如，查询如下的职工信息：
(1) 列出所有教师的名单；
对象关键码 key 对象存放地址 addr
(2) 已婚的女性职工有哪些人？
这些信息在数据表或文件中都存在，但都不是关键码，为回答以上问题，只能到表或文件中去顺序搜索，搜索效率极低。
因此，除主关键码外，可以 把一些经常搜索的属性设定为次关键码,并 针对每一个作为次关键码的属性,建立次索引 。
在次索引中，列出该属性的所有取值，并对每一个取值建立有序链表，把所有具有相同属性值的对象按存放地址递增的顺序或按主关键码递增的顺序链接在一起。
次索引的索引项由 次关键码,链表长度 和 链表本身 等三部分组成。
例如，为了回答上述的查询，我们可以分别建立“性别”、“婚否”和“职务”次索引。
性别次索引次关键码 男 女计 数 5 3
地址指针指针 03 08 17 24 47 51 83 95
婚否次索引次关键码 已婚 未婚计 数 5 3
地址指针指针 03 08 24 47 83 17 51 95
职务次索引次关键码 教师 教务员 实验员计 数 5 1 2
地址指针指针 08 24 47 51 83 03 17 95
(1) 列出所有教师的名单；
(2) 已婚的女性职工有哪些人？
通过顺序访问,职务,次索引中的,教师,
链，可以回答上面的查询 (1)。
通过对,性别,和,婚否,次索引中的,女性,链和,已婚,链进行求“交”运算，就能够找到所有既是女性又已婚的职工对象，
从而回答上面的查询 (2)。
倒排表是次索引的一种实现 。在表中所有次关键码的链都保存在次索引中，仅通过搜索次索引就能找到所有具有相同属性值的对象。
在次索引中 记录对象存放位臵的指针 可以用主关键码表示,可通过搜索次索引确定该对象的主关键码,再通过搜索主索引确定对象的存放地址 。
在倒排表中各个属性链表的长度大小不一,
管理比较困难。为此引入单元式倒排表。
在单元式倒排表中,索引项中不存放 对象的存储地址,存放 该对象所在硬件区域的标识 。
硬件区域可以是磁盘柱面、磁道或一个页块,以 一次 I / O 操作能存取的存储空间作为硬件区域 为最好。
为使索引空间最小,在索引中标识这个硬件区域时可以使用一个能转换成地址的二进制数,整个次索引形成一个 (二进制数的 ) 位矩阵 。
例如,对于记录学生信息的文件,次索引可以是如图所示的结构。二进位的值为 1 的硬件区域包含具有该次关键码的对象。
如果在硬件区域 1,…… 中有要求的对象。
然后将硬件区域 1,…… 等读入内存，在其中进行检索，确定就可取出所需对象。
硬 件 区 域
1 2 3 4 5 … 251 252 253 254 …
次关键码 1 男 1 0 1 1 1 … 1 0 1 1 …
( 性别 ) 女 1 1 1 1 1 … 0 1 1 0 …
次关键码 2 广东 1 0 0 1 0 … 0 1 0 0 …
( 籍贯 ) 北京 1 1 1 1 1 … 0 0 1 1 …
上海 0 0 1 1 1 … 1 1 0 0 …
……
次关键码 3 建筑 1 1 0 0 1 … 0 1 0 1 …
( 专业 ) 计算机 0 0 1 1 1 … 0 0 1 1 …
电机 1 0 1 1 0 … 1 0 1 0 …
……
单元式倒排表结构
m 路静态搜索树
当数据对象数目特别大，索引表本身也很大，
在内存中放不下，需要分批多次读取外存才能把索引表搜索一遍。
此时,可以建立索引的索引 (二级索引 )。二级索引可以常驻内存，二级索引中一个索引项对应一个索引块，登记该索引块的最大关键码及该索引块的存储地址。
1 0 1 1 1 …… 1 0 1 1
1 0 0 1 0 …… 0 1 0 0
A N D 1 1 0 0 1 …… 0 1 0 1
1 0 0 0 0 …… 0 0 0 0
如果二级索引在内存中也放不下，需要分为许多块多次从外存读入。可以建立二级索引的索引 (三级索引 )。这时，访问外存次数等于读入索引次数再加上 1次读取对象。
02 06 11 15 18 23 29 32 38 41 45 49 52 60 77 95
(06,) (15,) (23,) (32,) (41,) (49,) (60,) (95,)
(23,) (41,) (95,)
root
head
必要时,还可以有 4级索引,5极索引,… 。
这种多级索引结构形成一种 m 叉树。树中每一个分支结点表示一个索引块,它 最多存放 m 个索引项,每个索引项分别给出各子树结点 (低一级索引块 ) 的最大关键码和结点地址。
树的叶结点中各索引项给出在数据表中存放的对象的关键码和存放地址。这种 m叉树用来作为多级索引，就是 m路搜索树。
m路搜索树 可能是 静态索引结构,即结构在初始创建，数据装入时就已经定型，在整个运行期间，树的结构不发生变化。
多级索引结构形成 m 路搜索树
m路搜索树 还可能是 动态索引结构,即在整个系统运行期间,树的结构随数据的增删及时调整,以保持最佳的搜索效率。
数据区一级索引二级索引三级索引四级索引动态搜索结构
现在我们所讨论的 m 路搜索树多为可以动态调整的多路搜索树,它的一般定义为：
一棵 m 路搜索树,它或者是一棵空树,或者是满足如下性质的树：
根最多有 m 棵子树,并具有如下的结构：
n,P0,( K1,P1 ),( K2,P2 ),……,( Kn,Pn )
其中,Pi 是指向子树的指针,0? i? n < m; Ki
是关键码,1? i? n < m。 Ki < Ki+1,1? i < n。
动态的 m 路搜索树
在子树 Pi 中所有的关键码都 小于 Ki+1,且大于 Ki,0 < i < n。
在子树 Pn 中所有的关键码都 大于 Kn；
在子树 P0 中的所有关键码都 小于 K1。
子树 Pi 也是 m 路搜索树,0? i? n。
一棵 3路搜索树的示例
35
20 40a
b c d
e
25 3010 15 45 50
m 路搜索树的类定义
template <class Type> class Mtree { //基类
public:
Triple<Type> & Search ( const Type & );
protected:
Mnode<Type> root;
int m;
}
AVL树是 2路搜索树。如果已知 m 路搜索树的度 m 和它的 高度 h,则树中的 最大结点数 为
1
1
1 1
0
h
h
i
i m
m
m
(等比级数前 h 项求和 )
每个结点中 最多有 m-1 个关键码,在一棵高度为 h 的 m 路搜索树中关键码的最大个数为 mh+1-1。
高度 h=2 的二叉树,关键码最大个数为 7；
高度 h=3 的 3路搜索树,关键码最大个数为 34-1 = 80。
struct Triple {
Mnode<Type> * r; //结点地址指针
int i; int tag; //结点中关键码序号 i
}; //tag=0,搜索成功 ； tag=1,搜索不成功标识 m 路搜索树搜索结果的三元组表示
m 路搜索树上的搜索算法
在 m 路搜索树上的搜索过程是一个 在结点内搜索 和 自根结点向下逐个结点搜索 的交替的过程。
35
20 40a
b c d
e
25 3010 15 45 50
root
搜索 35
template <class Type> Triple<Type> &
Mtree<Type>,,Search ( const Type& x ) {
Triple result; //记录搜索结果三元组
GetNode ( root ); //读入根结点
Mnode <Type> *p = root,*q = NULL;
while ( p != NULL ) { //从根开始检测
int i = 0; p->key[(p->n)+1] = MAXKEY;
while ( p->key[i+1] < x ) i++; //结点内搜索
if ( p->key[i+1] == x ) { //搜索成功
result.r = p; result.i = i+1; result.tag = 0;
return result;
}
q = p; p = p->ptr[i]; //向下一层结点搜索
GetNode (p); //读入该结点
}
result.r = q; result.i = i; result.tag = 1;
return result; //搜索失败,返回插入位置
}
提高搜索树的路数 m,可以改善树的搜索性能 。 对于给定的关键码数 n,如果搜索树是平衡的,可以使 m 路搜索树的性能接近最佳 。 下面将讨论一种称之为 B 树的平衡的 m
路搜索树 。
B 树
一棵 m 阶 B 树是一棵平衡的 m 路搜索树,它或者是空树,或者是满足下列性质的树：
根结点至少有 2 个子女。
除根结点以外的所有结点 (不包括失败结点 )至少有?m/2?个子女。
所有的失败结点都位于同一层。
在 B 树中的“失败”结点是当搜索值 x不在树中时才能到达的结点。
事实上，在 B 树的每个结点中还包含有一组指针 D[m]，指向实际对象的存放地址。
30
K[i]与 D[i] (1? i? n < m) 形成一个 索引项
(K[i],D[i])，通过 K[i]可找到某个对象的存储地址 D[i]。
一棵 B 树是平衡的 m 路搜索树，但一棵平衡的 m 路搜索树不一定是 B 树。
35
20 40
25 3010 15 45 50
root
45 5035
4020
root
10 15 25
非 B 树 B 树
B 树的类定义和 B 树结点类定义
template <class Type> class Btree,
public Mtree<Type> {
//继承 m 路搜索树的所有属性和操作
public:
int Insert ( const Type& x );
int Remove ( const Type& x );
};
template <class Type> class Mnode {
// B 树结点类定义
private:
int n; //结点中关键码个数
Mnode<Type> *parent; //双亲指针
Type key[m+1]; //关键码数组 1?m-1
Mnode<Type> *ptr[m+1]; //子树指针数组
};
B 树的搜索算法
B 树的搜索算法继承了 m 路搜索树 Mtree上的搜索算法 。
B 树的搜索过程是一个在结点内搜索和循某一条路径向下一层搜索交替进行的过程 。
B 树的搜索时间与 B 树的阶数 m 和 B 树的高度 h直接有关,必须加以权衡 。
在 B 树上进行搜索,搜索成功所需的时间取决于关键码所在的层次 ; 搜索不成功所需的时间取决于树的高度 。
如果定义 B 树的高度 h 为失败结点所在的层次,需要了解树的高度 h 与树中的关键码个数 N 之间的关系 。
如果让 B 树每层结点个数达到最大,且设 关键码总数 为 N,则树的高度达到最小：
h =?logm( N*(m-2)/(m-1)+1)?-1
设在 m 阶 B 树中每层结点个数达到最少,则
B 树的高度可能达到最大。设树中关键码个数为 N，从 B 树的定义知：
0层 1 个结点
1层 至少 2 个结点
2层 至少 2?m / 2?个结点
3层 至少 2?m / 2? 2 个结点
如此类推,
h-1 层 至少有 2?m / 2? h-2 个结点。所有这些结点都不是失败结点。
高度 h与关键码个数 N之间的关系
若树中关键码有 N个,则失败结点数为 N+1。
这是因为失败数据一般与已有关键码交错排列。因此，有
N +1 = 失败结点数 = 位于第 h 层的结点数
2?m / 2? h-1
N? 2?m / 2? h-1-1
h-1? log?m / 2? ( (N +1) / 2 )
所有的非失败结点所在层次为 0? h-1。
示例：若 B 树的阶数 m = 199,关键码总数 N
= 1999999，则 B 树的高度 h 不超过
log100 1000000 +1= 4
m值的选择
如果提高 B 树的阶数 m,可以减少树的高度,
从而减少读入结点的次数,因而可减少读磁盘的次数。
事实上,m受到内存可使用空间的限制 。
当 m 很大超出内存工作区容量时,结点不能一次读入到内存,增加了读盘次数,也增加了结点内搜索的难度。
m值的选择,应使得在 B 树中找到关键码 x
的时间总量达到最小 。
这个时间由两部分组成：
从磁盘中读入结点所用时间
在结点中搜索 x 所用时间
根据定义,B 树的每个结点的大小都是固定的,结点内有 m-1 个索引项 (Ki,Di,Pi),1? i
< m。其中,Ki 所占字节数为?,Di 和 Pi 所占字节数为?，则 结点大小近似为 m(?+2?)
个字节 。读入一个结点所用时间为：
tseek + tlatency + m(? + 2?) ttran = a + bm
B 树的插入
B 树是从空树起,逐个插入关键码而生成的。
在 B 树，每个非失败结点的关键码个数都在
[?m/2?-1,m-1]
之间。
插入在 某个叶结点 开始。如果在关键码插入后结点中的 关键码个数超出了上界 m-1，则结点需要“分裂”，否则可以直接插入 。
实现结点“分裂”的原则是：
设结点 p 中已经有 m-1 个关键码，当再插入一个关键码后结点中的状态为
( m,P0,K1,P1,K2,P2,……,Km,Pm)
其中 Ki < Ki+1,1? i < m
这时必须把结点 p 分裂成两个结点 p 和 q，
它们包含的信息分别为：
结点 p：
(?m/2?-1,P0,K1,P1,……,K?m/2?-1,P?m/2?-1)
结点 q：
(m-?m/2?,P?m/2?,K?m/2?+1,P?m/2?+1,……,Km,Pm)
位于中间的关键码 K?m/2?与指向新结点 q 的指针形成一个二元组 ( K?m/2?,q )，插入到这两个结点的双亲结点中去。
结点“分裂”的示例
2 53 75
n P0 K1 P1 K2 P2
p
3 53 75 139
n P0 K1 P1 K2 P2 K3 P3
p
加入 139,
结点溢出
1 75
n P0 K1 P1
1 53
n P0 K1 P1
1 139
n P0 K1 P1
结点分裂
P q
49 75
示例,从空树开始加入关键码建立 3阶 B 树
n=1 加入 53
53
n=2 加入 75
53 75
n=3 加入 139
75
13953
n=5 加入 49,145
75
139 14549 53
n=6 加入 36
139 1455336
在插入新关键码时，需要自底向上分裂结点，最坏情况下从被插关键码所在叶结点到根的路径上的所有结点都要分裂。
若设 B 树的高度为 h,那么在 自顶向下 搜索到 叶结点 的过程中需要进行
h 次读盘。
n=7 加入 101
49
5336
139
145101
75
B 树的插入算法
template <class Type> int Btree<Type>,,
Insert ( const Type & x ) {
Triple<Type> loc = Search (x); //找 x的位置
if ( !loc.tag ) return 0; //找到,不再插入
Mnode<Type> *p = loc.r,*q; //未找到,插入
Mnode<Type> *ap = NULL,*t;
Type K = x; int j = loc.i; //插入位置 p,j
while (1) {
if ( p->n < m-1) { //当前结点未满
insertkey ( p,j,K,ap ); //(K,ap)插入 j后
PutNode (p); return 1; //写出
} //结点已满,分裂
int s = (m+1)/2; //求?m/2?
insertkey ( p,j,K,ap ); //(K,ap)插入 j后
q = new Mnode<Type>; //建立新结点
move ( p,q,s,m ); //从 p向 q 搬送
K = p->key[s]; ap = q; //分界码上移
if ( p->parent != NULL ) { //双亲不是根
t = p->parent; GetNode (t); //读入双亲
j = 0; t->key[(t->n)+1] = MAXKEY;
while ( t->key[j+1] < K ) j++; //找插入点
q->parent = p->parent;
PutNode (p); PutNode (q);
p = t;
} //继续 while(1) 循环,向上调整
else { //双亲是根
root = new Mnode<Type>; //创建新根
root->n = 1; root->parent = NULL;
root->key[1] = K; root->ptr[0] = p;
root->ptr[1] = ap;
q->parent = p->parent = root;
PutNode (p); PutNode (q);
PutNode (root); return 1; //跳出返回
}
}
}
当分裂一个非根的结点时需要向磁盘写出 2
个结点,当分裂根结点时需要写出 3 个结点。
如果我们所用的内存工作区足够大,使得在向下搜索时,读入的结点在插入后向上分裂时不必再从磁盘读入,那么,在完成一次插入操作时 需要读写磁盘的次数 =
= 找插入结点向下读盘次数 +
+ 分裂非根结点时写盘次数 +
+ 分裂根结点时写盘次数 =
= h+2(h-1)+3 =
= 3h+1。
B 树的删除
在 B 树上删除一个关键码时,首先需要找到这个关键码所在的结点,从中删去这个关键码。若该结点不是叶结点,且被删关键码为
Ki,1? i? n,则在删去该关键码之后,应以该结点 Pi 所指示子树中的最小关键码 x 来代替被删关键码 Ki 所在的位臵,然后在 x 所在的叶结点中删除 x。
在叶结点上的删除有 4 种情况。
① 被删关键码所在叶结点同时又是根结点且删除前该结点中关键码个数 n? 2，则直接删去该关键码并将修改后的结点写回磁盘。
② 被删关键码所在叶结点不是根结点且删除前该结点中关键码个数 nm/2?,则直接删去该关键码并将修改后的结点写回磁盘,删除结束。
③ 被删关键码所在叶结点删除前关键码个数 n
=?m/2?-1,若这时与该结点相邻的右兄弟
(或左兄弟 )结点的关键码个数 nm/2?，则可按以下步骤调整该结点、右兄弟 (或左兄弟 ) 结点以及其双亲结点，以达到新的平衡。
36 49m = 3 删除 36 49
55 58
删除 55简单删除
75 80
m = 3
删除 55
10 40 65
60 7030
50a
cb
d e f g h
58 75 8010 40 65
60 7030
50a
cb
d e f g h
将双亲结点中刚刚大于 (或小于 ) 该被删关键码的关键码 Ki (1? i? n) 下移；
将右兄弟 (或左兄弟 ) 结点中的最小 (或最大 )关键码上移到双亲结点的 Ki 位臵；
将右兄弟 (或左兄弟 ) 结点中的最左 (或最右 ) 子树指针平移到被删关键码所在结点中最后 (或最前 ) 子树指针位臵；
在右兄弟 (或左兄弟 ) 结点中，将被移走的关键码和指针位臵用剩余的关键码和指针填补、调整。再将结点中的关键码个数减
1。
结点联合调整
55 58 75 80
m = 3 删除 65
10 40 65
60 7030
50a
cb
d e f g h
55 58 8010 40 70
60 7530
50a
cb
d e f g h
调整 g,c,h
删除 65
70
删除 70
55 58 80
m = 3 删除 70
10 40
60 7530
50a
cb
d e f g h
55 8010 40 60
58 7530
50a
cb
d e f g h
调整 f,c,g
结点联合调整
④ 被删关键码所在叶结点删除前关键码个数
n =?m/2?-1,若这时与该结点相邻的右兄弟
(或左兄弟 )结点的关键码个数 n =?m/2?-1,
则必须按以下步骤合并这两个结点。
将双亲结点 p 中相应关键码下移到选定保留的结点中。若要合并 p 中的子树指针 Pi
与 Pi+1 所指的结点,且保留 Pi 所指结点,则把 p 中的关键码 Ki+1下移到 Pi 所指的结点中。
把 p 中子树指针 Pi+1 所指结点中的全部指针和关键码都照搬到 Pi 所指结点的后面。删去 Pi+1 所指的结点。
在结点 p 中用后面剩余的关键码和指针填补关键码 Ki+1 和指针 Pi+1。
修改结点 p 和选定保留结点的关键码个数。
在合并结点的过程中,双亲结点中的关键码个数减少了。
若双亲结点是根结点且结点关键码个数减到
0,则将该双亲结点删去,合并后保留的结点成为新的根结点 ; 否则将双亲结点与合并后保留的结点都写回磁盘,删除处理结束。
若双亲结点不是根结点且关键码个数减到
m/2?-2，又要与它自己的兄弟结点合并,重复上面的合并步骤。最坏情况下这种结点合并处理要自下向上直到根结点。
55
删除 55结点合并
80
m = 3 删除 55
10 40 60
58 7530
50a
cb
d e f g h
合并 f,g
58 60 8010 40
7530
50a
cb
d e f h
8055
删除 80结点合并
m = 3 删除 80
10 40 60
58 7530
50a
cb
d e f g h
合并 g,h
60 755510 40
5830
50a
cb
d e f h
55
非叶结点删除删除 50
删除 55
55 58 75 80
m = 3 删除 50
10 40 65
60 7030
50a
cb
d e f g h
58 75 80
删除 55
10 40 65
60 7030
a
cb
d e f g h
用 55取代用 58取代
58
75 8010 40 65
60 7030
a
cb
d e f g h
合并 f,g
58
75 8010 40 60 65
7030
a
cb
d e f h
结点合并与调整删除 70
58
8010 40 60 65
7530
a
cb
d e f h
删除 70
用 75取代删除 75
58
10 40 60 65
8030
a
cb
d e f h
删除 75
用 80取代调整 f,c,h
58
8010 40 60
6530
a
cb
d e f h
删除 10
8030 40 60f h
58 65
d
b
B 树的关键码删除算法
template <class Type> int Btree<Type>,:
Delete ( const Type & x ) {
Triple<Type> loc = Search (x); //搜索 x
if ( loc.tag ) return 0; //未找到,不删除
Mnode<Type> *p = loc.r,*q,*s; //找到,删除
int j = loc.i;
if ( p->ptr[j] != NULL ) { //非叶结点
s = p->ptr[j]; GetNode (s); q = p;
while ( s != NULL ) { q = s; s = s->ptr[0]; }
p->key[j] = q->key[1]; //从叶结点替补
compress ( q,1 ); //在叶结点删除
p = q; //转化为叶结点的删除
}
else compress ( p,j ); //叶结点,直接删除
int d = (m+1)/2; //求?m/2?
while (1) { //调整或合并
if ( p->n < d -1 ) { //小于最小限制
j = 0; q = p->parent; //找到双亲
GetNode (q);
while ( j <= q->n && q->ptr[j] != p )
j++;
if ( !j ) LeftAdjust ( p,q,d,j ); //调整
else RightAdjust ( p,q,d,j );
p = q; //向上调整
if ( p == root ) break;
}
else break;
}
if ( !root->n ) { //调整后根的 n减到 0
p = root->ptr[0];
delete root; root = p; //删根
root->parent = NULL; //新根
}
}
B+树
一棵 m 阶 B+树可以定义如下：
树中每个非叶结点 最多有 m 棵子树 ；
根结点 (非叶结点 )至少有 2 棵子树 。 除根结点外,其它的非叶结点至少有?m/2? 棵子树 ; 有 n 棵子树的非叶结点有 n-1 个关键码 。
所有叶结点都处于同一层次上,包含了全部关键码及指向相应数据对象存放地址的指针,且叶结点本身按关键码从小到大顺序链接；
叶结点的子树棵数 n 可以多于 m,可以少于 m,视关键码字节数及对象地址指针字节数而定。若设结点可容纳最大关键码数为 m1,则指向对象的地址指针也有 m1 个。
10 15 18 20 22 23 31 33 45 48 52
18 23
33
33
叶结点中的子树棵数 n 应满足
n? [?m1/2?,m1]。
若根结点同时又是叶结点,则结点格式同叶结点。
所有的非叶结点可以看成是索引部分,结点中关键码 Ki 与指向子树的指针 Pi 构成对子树 (即下一层索引块 )的索引项 ( Ki,Pi )，
Ki 是子树中最小的关键码。
特别地,子树指针 P0 所指子树上所有关键码均小于 K1。结点格式同 B 树。
叶结点中存放的是对实际数据对象的索引。
在 B+树中有两个头指针,一个指向 B+ 树的根结点，一个指向关键码最小的叶结点。
可对 B+树进行两种搜索运算：
循叶结点链 顺序搜索
另一种是从根结点开始,进行自顶向下,
直至叶结点的 随机搜索 。
在 B+树上进行随机搜索、插入和删除的过程基本上与 B 树类似。只是在搜索过程中，
如果非叶结点上的关键码等于给定值，搜索并不停止，而是继续沿右指针向下，一直查到叶结点上的这个关键码。
B+树的搜索分析类似于 B 树。
B+树的插入仅在叶结点上进行 。 每插入一个 (关键码 -指针 )索引项后都要判断结点中的子树棵数是否超出范围。
当插入后结点中的子树棵数 n > m1 时,需要将叶结点分裂为两个结点,它们的关键码分别为?(m1+1)/2?和?(m1+1)/2?。
它们的双亲结点中应同时包含这两个结点的最小关键码和结点地址。此后,问题归于在非叶结点中的插入了。
3个关键码的 B+树
10 12 23
加入关键码 33,结点分裂
10 12 23 33
23
10 12 18 20 22 23 33
18 23
加入更多的关键码
在非叶结点中关键码的插入与叶结点的插入类似,但非叶结点中的子树棵数的上限为
m,超出这个范围就需要进行结点分裂。
在做根结点分裂时,因为没有双亲结点,就必须创建新的双亲结点,作为树的新根。这样树的高度就增加一层了。
B+树的删除仅在叶结点上进行 。当在叶结点上删除一个 (关键码 -指针 )索引项后,结点中的子树棵数仍然不少于?m1/2?，这属于简单删除,其上层索引可以不改变。
如果删除的关键码是该结点的最小关键码,
但因在其上层的副本只是起了一个引导搜索的“分界关键码”的作用,所以上层的副本仍然可以保留。
如果在叶结点中删除一个 (关键码 -指针 )索引项后，该结点中的子树棵数 n 小于结点子树棵数的下限?m1/2?，必须做结点的调整或合并工作。
删除 18
10 15 18 20 22 23 31 33 45 48 52
18 23
33
33
10 15 20 22 23 31 33 45 48 52
18 23
33
33
删除关键码 18上层索引不改
10 15 18 20 22 23 31 33 45 48 52
18 23
33
33
15 18 20 22 23 31 33 45 48 52
20 23
33
33
删除关键码 10,18移入结点,索引改 20
删除 10
如果右兄弟结点的子树棵数已达到下限
m1/2?,没有多余的关键码可以移入被删关键码所在的结点,必须进行两个结点的合并 。 将右兄弟结点中的所有 (关键码 -指针 )
索引项移入被删关键码所在结点,再将右兄弟结点删去 。
结点的合并将导致双亲结点中,分界关键码,的减少,有可能减到非叶结点中子树棵数的下限?m/2? 以下 。 这样将引起非叶结点的调整或合并 。 如果根结点的最后两个子女结点合并,树的层数就会减少一层 。
10 15 18 20 22 23 31 33 45 48 52
18 23
33
33
15 18 20 22 23 31
20 23 45
删除关键码 33,右边两结点合并,影响到非叶结点合并,可能直到根结点,导致高度减少删除 33
45 48 52
散列 (Hashing)
在计算科学中把词典当作一种抽象数据类型。
在讨论词典抽象数据类型时，把词典定义为
<名字 -属性 >对的集合。
在现实中,经常遇到按给定的值进行查询的事例。为此,必须在开发相应软件时考虑在记录的存放位臵和用以标识它的数据项 (称为关键码 )之间的对应关系,从而选择适当的数据结构,很方便地根据记录的关键码检索到对应记录的信息。
词典 (Dictionary)的抽象数据类型
根据问题的不同,可以为名字和属性赋予不同的含义。
例如,在图书馆检索目录中,名字是书名,属性是索书号及作者等信息 ; 在计算机活动文件表中,名字是文件名,属性是文件地址、
大小等信息。
词典的抽象数据类型
const int DefaultSize = 26;
template<class Name,class Attribute>
class Dictionary {
public:
Dictionary ( int size = DefaultSize );
int IsIn ( Name name );
Attribute * Find ( Name name );
void Insert ( Name name,Attribute attr );
void Remove ( Name name );
}
在词典的所有操作中，最基本的只有 3 种：
Find (搜索 ),Insert (插入 ),Remove (删除 )。
在选择词典的表示时，必须确保这几个操作的实现。
通常，用 文件 (表格 ) 来表示实际的对象集合,
用 文件记录 (表格的表项 )来表示单个对象。
这样,词典中的 <名字 -属性 >对 将被存于 记录
(表项 )中，通过表项的 关键码 ( <名字 -属性
>对 的名字 ) 来标识该表项。
表项的存放位臵及其关键码之间的对应关系可以用一个二元组表示：
( 关键码 key，表项位臵指针 addr )
这个二元组构成搜索某一指定表项的索引项。
考虑到搜索效率,可以用顺序表方式、二叉搜索树或多路搜索树方式组织词典。本节讨论另一种组织词典的方法,即散列表结构。
静态散列方法
散列方法在 表项存储位臵 与 其关键码 之间建立一个 确定的对应函数关系 Hash( )，使每个关键码与结构中一个唯一存储位臵相对应：
Address ＝ Hash ( Rec.key )
在搜索时,先对表项的关键码进行函数计算,
把函数值当做表项的存储位臵,在结构中按此位臵取表项比较。若关键码相等,则搜索成功。在存放表项时,依相同函数计算存储位臵,并按此位臵存放。这种方法就是散列方法。
在散列方法中使用的转换函数叫做 散列函数 。
按此方法构造出来的表或结构就叫做 散列表 。
使用散列方法进行搜索不必进行多次关键码的比较,搜索速度比较快,可以直接到达或逼近具有此关键码的表项的实际存放地址。
散列函数是一个压缩映象函数 。关键码集合比散列表地址集合大得多。因此有可能经过散列函数的计算，把不同的关键码映射到同一个散列地址上，这就产生了 冲突 。
示例：有一组表项，其关键码分别是
12361,07251,03309,30976
采用的散列函数是
hash(x) = x % 73 + 13420
其中，,%” 是除法取余操作。
则有,hash(12361) = hash(07250) = hash(03309)
= hash(30976) = 13444。 就是说,对不同的关键码,通过散列函数的计算,得到了同一散列地址。 我们称这些产生冲突的散列地址相同的不同关键码为 同义词 。
由于关键码集合比地址集合大得多,冲突很难避免。 所以对于散列方法,需要讨论以下两个问题：
构造散列函数时的几点要求：
散列函数应是简单的，能在较短的时间内计算出结果。
散列函数的定义域必须包括需要存储的全部关键码,如果散列表允许有 m 个地址时,其值域必须在 0 到 m-1 之间。
散列函数
对于给定的一个关键码集合,选择一个计算简单且地址分布比较均匀的散列函数,避免或尽量减少冲突；
拟订解决冲突的方案。
① 直接定址法此类函数取关键码的某个线性函数值作为散列地址：
Hash ( key ) ＝ a * key + b { a,b为常数 }
这类散列函数是一对一的映射，一般不会产生冲突。但是，它要求散列地址空间的大小与关键码集合的大小相同。
散列函数计算出来的 地址应能均匀分布在整个地址空间中,若 key 是从关键码集合中随机抽取的一个关键码,散列函数应能以同等概率取 0 到 m-1 中的每一个值。
示例：有一组关键码如下,{ 942148,941269,
940527,941630,941805,941558,942047,
940001 }。 散列函数为
Hash (key) = key - 940000
Hash (942148) = 2148 Hash (941269) = 1269
Hash (940527) = 527 Hash (941630) = 1630
Hash (941805) = 1805 Hash (941558) = 1558
Hash (942047) = 2047 Hash (940001) = 1
可以按计算出的地址存放记录。
② 数字分析法
设有 n 个 d 位数,每一位可能有 r 种不同的符号。这 r 种不同的符号在各位上出现的频率不一定相同。 可根据散列表的大小,选取其中各种符号分布均匀的若干位作为散列地址。
计算各位数字中符号分布均匀度? k 的公式,
其中,表示第 i 个符号在第 k 位上出现的次数,n/r 表示各种符号在 n 个数中均匀出现的期望值。计算出的? k 值越小，表明在该位 (第 k 位 ) 各种符号分布得越均匀。
r
i
k
ik rn
1
2)/(αλ
kiα
9 4 2 1 4 8 ① 位,? 1 = 57.60
9 4 1 2 6 9 ② 位,? 2 = 57.60
9 4 0 5 2 7 ③ 位,? 3 = 17.60
9 4 1 6 3 0 ④ 位,? 4 = 5.60
9 4 1 8 0 5 ⑤ 位,? 5 = 5.60
9 4 1 5 5 8 ⑥ 位,? 6 = 5.60
9 4 2 0 4 7
9 4 0 0 0 1
① ② ③ ④ ⑤ ⑥
若散列表地址范围有 3 位数字,取各关键码的 ④⑤⑥ 位做为记录的散列地址。也可以把第①，②,③ 和第⑤位相加,舍去进位位,变成一位数,与第④,⑥ 位合起来作为散列地址。
数字分析法仅适用于事先明确知道表中所有关键码每一位数值的分布情况，它完全依赖于关键码集合。如果换一个关键码集合，选择哪几位要重新决定。
③ 除留余数法
设散列表中允许地址数为 m,取一个不大于
m,但最接近于或等于 m 的质数 p 作为除数,
利用以下函数把关键码转换成散列地址：
hash ( key ) = key % p p? m
其中,“%” 是整数除法取余的运算，要求这时的质数 p 不是接近 2的幂。
示例,有一个关键码 key = 962148,散列表大小 m = 25,即 HT[25]。取质数 p= 23。散列函数 hash ( key ) = key % p。则散列地址为
hash ( 962148 ) = 962148 % 23 = 12。
可以按计算出的地址存放记录。需要注意的是,使用上面的散列函数计算出来的地址范围是 0到 22,因此,从 23到 24这几个散列地址实际上在一开始是不可能用散列函数计算出来的,只可能在处理溢出时达到这些地址。
④ 平方取中法
此方法在词典处理中使用十分广泛。
它先计算构成关键码的标识符的内码的平方,
然后按照散列表的大小取中间的若干位作为散列地址 。
设标识符可以用一个计算机字长的内码表示 。
因为内码平方数的中间几位一般是由标识符所有字符决定,所以对不同的标识符计算出的散列地址大多不相同,即使其中有些字符相同 。
在平方取中法中,一般取散列地址为 2 的某次幂 。 例如,若散列地址总数取为 m = 2r,则对内码的平方数取中间的 r 位 。 如果 r = 3，
所取得的散列地址参看图的最右一列 。
标识符 内码 内码的平方 散列地址
A 01 01 001
A1 0134 20420 042
A9 0144 23420 342
B 02 4 004
DMAX 04150130 21526443617100 443
DMAX1 0415013034 5264473522151420 352
AMAX 01150130 135423617100 236
AMAX1 0115013034 3454246522151420 652
标识符的八进制内码表示及其平方值
⑤ 折叠法
此方法把关键码自左到右分成 位数相等 的几部分,每一部分的位数应与散列表地址位数相同,只有最后一部分的位数可以短一些。
把这些部分的数据叠加起来,就可以得到具有该关键码的记录的散列地址。
有两种叠加方法：
移位法 —把各部分的最后一位对齐相加；
分界法 —各部分不折断,沿各部分的分界来回折叠,然后对齐相加,将相加的结果当做散列地址。
示例,设给定的关键码为 key = 23938587841,
若 存储空间限定 3 位,则划分结果为每段 3
位,上述关键码可划分为 4段：
239 385 878 41
把超出地址位数的最高位删去,仅保留最低的 3位，做为可用的散列地址。
移位法分界法
一般当关键码的位数很多,而且关键码每一位上数字的分布大致比较均匀时,可用这种方法得到散列地址 。
以上介绍了几种常用的散列函数 。 在实际工作中应根据关键码的特点,选用适当的方法 。 有人曾用,轮盘赌,的统计分析方法对它们进行了模拟分析,结论是平方取中法最接近于,随机化,。
处理冲突的闭散列方法因为任一种散列函数也不能避免产生冲突，
因此选择好的解决冲突的方法十分重要。
为了减少冲突，对散列表加以改造。若设散列表 HT 有 m 个地址,将其改为 m 个桶 。其桶号与散列地址一一对应,第 i (0? i < m) 个桶的桶号即为第 i 个散列地址。
每个桶可存放 s 个表项,这些表项的关键码互为同义词。如果对两个不同表项的关键码用散列函数计算得到同一个散列地址，就产生了冲突，它们可以放在同一个桶内的不同位臵。
只有当桶内所有 s 个表项位臵都放满表项后再加入表项才会产生溢出 。
通常桶的大小 s 取的比较小,因此在桶内大多采用顺序搜索。
闭散列也叫做开地址法。在闭散列情形,所有的桶都直接放在散列表数组中 。 因此每个桶只有一个表项 ( s = 1 )。
若设散列表中各桶的编址为 0 到 m-1,当要加入一个表项 R2时,用它的关键码 R2.key,
通过散列函数 hash ( R2.key ) 的计算，得到它的存放桶号 j。
但在存放时发现此桶已被另一个表项 R1 占据,
发生了冲突,必须处理冲突。为此,需把 R2 存放到表中“下一个”空桶中。 如果表未被装满,则在允许的范围内必定还有空桶。
(1) 线性探查法 (Linear Probing)
假设给出一组表项，它们的关键码为 Burke,
Ekers,Broad,Blum,Attlee,Alton,Hecht,
Ederly。采用的散列函数是：取其第一个字母在字母表中的位臵。
Hash (x) = ord (x) - ord (?A?)
//ord ( ) 是求字符内码的函数
可得 Hash (Burke) = 1 Hash (Ekers) = 4
Hash (Broad) = 1 Hash (Blum) = 1
Hash (Attlee) = 0 Hash (Hecht) = 7
Hash (Alton) = 0 Hash (Ederly) = 4
设散列表 HT[26],m = 26。采用 线性探查法处理冲突,则散列结果如图所示。
0 1 2 3 4
Attlee Burke Broad Blum Ekers
Alton Ederly Hecht
5 6 7 8 9
(1) (1) (2) (3) (1)
(6) (3) (1)
需要搜索或加入一个表项时,使用散列函数计算桶号：
H0 = hash ( key )
一旦发生冲突，在表中顺次向后寻找,下一个”空桶 Hi 的递推公式为：
Hi = ( Hi-1 +1 ) % m,i =1,2,…,m-1
即用以下的线性探查序列在表中寻找,下一个”空桶 的桶号：
H0 +1,H0 +2,…,m-1,0,1,2,…,H0-1
亦可写成如下的通项公式：
Hi = ( H0 + i ) % m,i =1,2,…,m-1
当发生冲突时,探查下一个桶。当循环 m-1
次后就会回到开始探查时的位臵,说明待查关键码不在表内,而且表已满,不能再插入新关键码。
用 平均搜索长度 ASL (Averagy Search Length)
衡量散列方法的搜索性能。
根据搜索成功与否，它又有 搜索成功的平均搜索长度 ASLsucc和 搜索不成功的平均搜索长度 ASLunsucc之分。
搜索成功的平均搜索长度 ASLsucc 是指 搜索到表中已有表项的平均探查次数 。它是找到表中各个已有表项的探查次数的平均值。
搜索不成功的平均搜索长度 ASLunsucc 是指在表中搜索不到待查的表项，但找到插入位臵的平均探查次数 。它是表中所有可能散列到的位臵上要插入新元素时为找到空桶的探查次数的平均值。
在使用线性探查法对示例进行搜索时,搜索成功的平均搜索长度为：
搜索不成功的平均搜索长度为,
8
1
.
8
181)361321(1
8
1
8
1
i
CiA S L s u c c
.266226 1823456789A S L u n s u c c
下面是用 线性探查法 在散列表 ht 中搜索给定值 x 的算法。如果查到某一个 j，使得
ht[j].info == Active && ht[j].Element == x
则搜索成功；否则搜索失败。造成失败的原因可能是表已满，或者是原来有此表项但已被删去，或者是无此表项且找到空桶。
class HashTable {
//用线性探查法处理冲突时散列表类的定义
public:
enum KindOfEntry { Active,Empty,Deleted };
HashTable ( ),TableSize ( DefaultSize )
{ AllocateHt ( ); CurrentSize = 0; }
~HashTable ( ) { delete [ ] ht; } //析构函数
const HashTable & operator = //表复制
( const HashTable & ht2 );
int Find ( const Type& x ); //搜索
int Insert ( const Type& x ); //插入
int Remove ( const Type& x ); //删除
int IsIn ( const Type& x ) //判存在
{ return ( i = Find (x) ) >= 0? 1,0; }
void MakeEmpty ( ); //置空
private:
struct HashEntry { //散列表表项
Type Element; //表项关键码
KindOfEntry info; //三种状态
int operator== ( HashEntry& ); //判相等
int operator!= ( HashEntry & ); //判不等
HashEntry ( ),info (Empty ) { } //构造函数
HashEntry (const Type& E,KindOfEntry
i = Empty ),Element (E),info (i) { }
};
enum { DefualtSize = 11 }
HashEntry *ht; //散列表数组
int CurrentSize,TableSize; //当前及最大桶数
void AllocateHt ( ) //分配空间
{ ht = new HashEntry[TableSize ]; }
int FindPos ( const Type & x ) const;
} //散列函数
template <class Type> int HashTable <Type>::
Find ( const Type& x ) {
//线性探查法的搜索算法,函数返回找到位置 。
//若返回负数可能是空位,若为 -TableSize则失败 。
int i = FindPos ( x ),j = i; //计算散列地址
while ( ht[j].info != Empty &&
ht[j].Element != x ){
j = ( j + 1 ) % TableSize; //冲突,找空桶
if ( j == i ) return -TableSize; //失败,表满
}
if ( ht[j].info == Active ) return j; //成功
else -j; //失败
}
在利用散列表进行各种处理之前,必须首先将散列表中原有的内容清掉 。 只需将表中所有表项的 info域臵为 Empty即可 。
散列表存放的表项不应有重复的关键码 。 在插入新表项时,如果发现表中已经有关键码相同的表项,则不再插入 。
在闭散列情形下不能真正删除表中已有表项 。
删除表项会影响其他表项的搜索 。 若把关键码为 Broad的表项真正删除,把它所在位臵的
info域臵为 Empty,以后在搜索关键码为 Blum
和 Alton的表项时就查不下去,会错误地判断表中没有关键码为 Blum和 Alton的表项 。
若想删除一个表项,只能给它做一个删除标记 deleted进行逻辑删除,不能把它真正删去。
逻辑删除的副作用 是：在执行多次删除后,
表面上看起来散列表很满,实际上有许多位臵没有利用。
template <class Type>
void HashTabe<Type>,,MakeEmpty ( ) {
//置表中所有表项为空
for ( int i = 0; i < TableSize; i++)
ht[i].info = Empty;
CurrentSize = 0;
}
template <class Type>
const HashTable <Type>& HashTable<Type>,:
operator = ( const HashTable<Type>& ht2 ) {
//重载函数：从散列表 ht2 复制到当前散列表
if ( this != &ht2 ) {
delete [ ] ht;
TableSize = ht2.TableSize; AllocateHt ( );
for ( int i = 0; i < TableSize; i++ )
ht[i] = ht2.ht[i];
CurrentSize = ht2.CurrentSize;
}
return *this;
}
template <class Type> int HashTable<Type>::
Insert ( const Type & x ) {
//将新表项 x 插入到当前的散列表中
if ( ( int i = Find (x) ) >= 0 ) return 0; //不插入
else if ( i != -TableSize &&
ht[-i].info != Active ) { //在 -i 处插入 x
ht[-i].Element = x;
ht[-i].info = Active;
CurrentSize++;
return 1;
}
else return 0;
}
template <class Type> int HashTable <Type>,,
Remove ( const Type& x ) {
//在当前散列表中删除表项 x
if ( ( int i = Find (x) ) >= 0 ) { //找到,删除
ht[i].info = deleted; //做删除标记
CurrentSize--;
return 1;
}
else return 0;
}
线性探查方法容易产生,堆积,,不同探查序列的关键码占据可用的空桶,为寻找某一关键码需要经历不同的探查序列,导致搜索时间增加。
算法分析
设散列表的 装填因子 为? = n / (s*m),其中
n 是表中已有的表项个数,s 是每个桶中最多可容纳表项个数,m是表中的桶数 。
可用? 表明散列表的装满程度 。 越大,表中表项数越多,表装得越满,发生冲突可能性越大 。
通过对线性探查法的分析可知,为搜索一个关键码所需进行的探查次数的期望值 P 大约是 (2-?)/(2-2?)。 虽然平均探查次数较小,
但在最坏情况下的探查次数会相当大 。
(2) 二次探查法 (quadratic probing)
为改善“堆积”问题,减少为完成搜索所需的平均探查次数,可使用二次探查法。
通过某一个散列函数对表项的关键码 x 进行计算,得到桶号,它是一个非负整数。
H0 = hash(x)
二次探查法在表中寻找“下一个”空桶的公式：
Hi = (H0 + i 2 ) % m,
Hi = (H0 - i 2 ) % m,i = 1,2,…,( m-1)/2
式中的 m 是表的大小，它应是一个值为
4k+3 的质数，其中 k 是一个整数。 如 3,7,
11,19,23,31,43,59,127,251,503,… 。
探查序列如 H0,H0+1,H0-1,H0+4,H0-4,… 。
在做 (H0- i2 ) % m 的运算时,当 H0- i2 < 0 时,
运算结果也是负数 。 实际算式可改为
j = (H0- i2 ) % m,if ( j < 0 ) j += m
示例：给出一组关键码 { Burke,Ekers,
Broad,Blum,Attlee,Alton,Hecht,Ederly }。
散列函数为,Hash (x)＝ ord (x)－ ord ('A')
用它计算可得
Hash (Burke) = 1 Hash (Ekers) = 4
Hash (Broad) = 1 Hash (Blum) = 1
Hash (Attlee) = 0 Hash (Hecht) = 7
Hash (Alton) = 0 Hash (Ederly) = 4
因为可能桶号是 0? 25,取满足 4k+3 的质数，
表的长度为 TableSize = 31，利用二次探查法得到的散列结果如图所示。
0 1 2 3 4 5
Blum Burke Broad Ekers Ederly
Hecht
6 7 8 9 10 11
Alton Attlee
(3) (1) (2) (1) (2)
(1)
25 26 27 28 29 30
(5) (3)
利用二次探查法处理溢出
使用 二次探查法 处理冲突时的 搜索成功的平均搜索长度 为：
搜索不成功的平均搜索长度 为：
.8183)512121(38181
8
1
i
CiA S L s u c c
26
402 0)22325(6
26
1A S L u n s u c c
设散列表桶数为 m,待查关键码为 x,第一次通过散列函数计算出的桶号为 H0=hash(x)。当发生冲突时，第 i-1 次和第 i 次计算出来的
“下 一个”桶号分别为：
,% ) 1)( (
,% ) 1)( (
2
0
( 1 )
1
2
0
( 0 )
1
miHH
miHH
i
i
,% ) (
,% ) (
2
0
( 1 )
2
0
( 0 )
miHH
miHH
i
i
相减，可以得到：
,% ) 1*2 (
,% ) 1*2 (
( 1 )
1
( 1 )
( 0 )
1
( 0 )
miHH
miHH
ii
ii
从而
,% ) 1*2 (
,% ) 1*2 (
( 1 )
1
( 1 )
( 0 )
1
( 0 )
miHH
miHH
ii
ii
只要知道上一次的桶号 和,当 i 增加 1
时可以从 和 简单地导出 和,
不需要每次计算 i 的平方 。
在冲突处理算法 Find 中,首先求出 H0作为当前桶号 CurrentPos,当发生冲突时求,下一个,桶号,i = 1。
此时用一个标志 odd 控制是加 i2 还是减 i2 。
若 odd == 0 加 i 2,并臵 odd = 1；
若 odd == 1 减 i 2,并臵 odd = 0。
下次 i 进一后,又可由 odd 控制先加后减 。
处理冲突的算法
(0)1?iH (1)1?iH
(0)1?iH (1)1?iH (1)iH(1)iH
template <class Type> int HashTable<Type>,:
Find ( const Type& x ) {
int i = 0,odd = 0;
int CurrentPos = HashPos ( x ); //初始 桶号
while ( ht[CurrentPos].info != Empty &&
ht[CurrentPos].Element != x ) { //冲突
if ( !odd ) { // odd == 0 加 i 2
CurrentPos = ( CurrentPos + 2* i-1) %
TableSize;
odd = 1;
}
else { // odd == 1 减 i 2
CurrentPos = ( CurrentPos-2*i+1 ) %
TableSize;
odd = 0;
}
}
LastFindOK = ht[CurrentPos].info == Active;
return CurrentPos;
}
可以证明,当 表的长度 TableSize为质数 且 表的装填因子?不超过 0.5 时,新的表项 x 一定能够插入,且任何一个位臵不会被探查两次。，
只要表中至少有一半空，就不会有表满问题。
在搜索时可以不考虑表满的情况 ; 但在插入时 必须确保表的装填因子?不超过 0.5。 如果超出,必须将表长度扩充一倍,进行表的分裂 。
在删除一个表项时,为确保搜索链不致中断,
也只能做表项的逻辑删除,即将被删表项的标记 info改为 Deleted。
(3) 双散列法
使用双散列方法时,需要两个散列函数 。
第一个散列函数 Hash( ) 按表项的关键码
key 计算表项所在的桶号 H0 = Hash(key)。
一旦冲突,利用第二个散列函数 ReHash( )
计算该表项到达,下一个,桶的移位量 。 它的取值与 key 的值有关,要求它的取值应是小于地址空间大小 TableSize,且与
TableSize 互质的正整数 。
若设表的长度为 m = TableSize,则在表中寻找,下一个,桶的公式为：
j = H0 = Hash(key),p = ReHash(key)；
j = ( j + p ) % m；
p是小于 m且与 m互质的整数
利用双散列法,按一定的距离,跳跃式地寻找
“下一个”桶,减少了“堆积”的机会。
双散列法的探查序列也可写成：
Hi = (H0 + i * ReHash(key) ) % m，
i =1,2,…,m-1
最多经过 m-1次探查,它会遍历表中所有位臵,回到 H0 位臵。
示例：给出一组表项关键码 { 22,41,53,46,
30,13,01,67 }。散列函数为：
Hash(x)＝ (3x) % 11。
散列表为 HT[0..10],m = 11。因此，再散列函数为 ReHash(x) = (7x) % 10 +1。
Hi = ( Hi-1 + (7x) % 10 +1 ) % 11,i = 1,2,?
H0(22) = 0 H0(41) = 2 H0(53) = 5
H0(46) = 6 H0(30) = 2 冲突 H1 = (2+1) = 3
H0(13) = 6 冲突 H1 = (6+2) = 8
H0(01) = 3 冲突 H1 = (3+8) = 0 冲突 H2 =
(0+8) = 8 冲突 H3 = (8+8) = 5 冲突 H4 =
(5+8) = 2 冲突 H5 = (2+8) = 10
H0(67) = 3 冲突 H1 = (3+10) = 2 冲突 H2 =
(2+10) = 1
22 67 41 30 53 46 13 01
(1) (3) (1) (2) (1) (1) (2) (6)
0 1 2 3 4 5 6 7 8 9 10
1 8 2 5 3 4 6 7
搜索成功的平均搜索长度
搜索不成功的平均搜索长度
每一散列位臵的移位量有 10种,1,2,?,
10。先计算每一散列位臵各种移位量情形下找到下一个空位的比较次数,求出平均值；
再计算各个位臵的平均比较次数的总平均值。
22 67 41 30 53 46 13 01
(1) (3) (1) (2) (1) (1) (2) (6)
0 1 2 3 4 5 6 7 8 9 10
8
176)211213(1
8
1A S L s u c c
Rehash( )的取法很多 。 例如,当 m是质数时,
可定义
ReHash(key) = key % (m-2) +1
ReHash(key) =?key / m? % (m-2)+1
当 m 是 2 的方幂时,ReHash(key) 可取从 0
到 m-1 中的任意一个奇数。
处理冲突的开散列方法 — 链地址法
开散列方法首先对关键码集合用某一个散列函数计算它们的存放位臵 。
若设散列表地址空间的所有位臵是从 0 到
m-1,则关键码集合中的所有关键码被划分为 m个子集,具有相同地址的关键码归于同一子集 。 我们称同一子集中的关键码互为同义词 。 每一个子集称为一个桶 。
通常各个桶中的表项通过一个单链表链接起来,称之为同义词子表 。 所有桶号相同的表项都链接在同一个同义词子表中,各链表的表头结点组成一个向量 。
向量的元素个数与桶数一致。桶号为 i 的同义词子表的表头结点是向量中的第 i 个元素。
示例：给出一组表项关键码 { Burke,Ekers,
Broad,Blum,Attlee,Alton,Hecht,Ederly }。
散列函数为,Hash (x)＝ ord (x)－ ord ('A')。
用它计算可得：
Hash (Burke) = 1 Hash (Ekers) = 4
Hash (Broad) = 1 Hash (Blum) = 1
Hash (Attlee) = 0 Hash (Hecht) = 7
Hash (Alton) = 0 Hash (Ederly) = 4
散列表为 HT[0..25],m = 26。
0
1
2
3
4
5
6
7
8
9
Attlee Alton
Burke Broad Blum
Ekers Ederly
Ekers 8
13
8
1*33*24*1
s u c cA S L
26
34
18)*12
113114(3
26
1
u n s u c cA S L
通常,每个桶中的同义词子表都很短,设有
n 个关键码通过某一个散列函数,存放到散列表中的 m 个桶中 。 那么每一个桶中的同义词子表的平均长度为 n / m。 以搜索平均长度为 n / m 的同义词子表代替了搜索长度为 n
的顺序表,搜索速度快得多 。
利用链地址法处理溢出时的类定义
template <class Type> class ListNode { //链结点
friend HashTable;
private:
Type key; //关键码
ListNode *link; //链指针
};
typedef ListNode<Type> *ListPtr;
class HashTable { //散列表的类定义
public:
HashTable( int size = defaultsize ) //构造函数
{ buckets = size; ht = new ListPtr[buckets]; }
private:
int buckets; //桶数
ListPtr <Type> *ht; //散列表数组的头指针
};
循链搜索的算法
template<class Type>
Type * HashTable<Type>:,
Find ( const Type & x,) {
int j = HashFunc ( x,buckets ); //初始桶号
ListPtr<Type> * p = ht[j]; //桶地址
while ( p != NULL )
if ( p->key == x ) return & p->key;
else p = p->link;
return 0;
}
其它如插入,删除操作可参照单链表的插入,
删除等算法来实现 。
应用开散列法处理冲突,需要增设链接指针,
似乎增加了存储开销 。 事实上,由于闭散列法必须保持大量的空闲空间以确保搜索效率,
如二次探查法要求装填因子 0.5,而表项所占空间又比指针大得多,所以使用开散列法反而比闭散列法节省存储空间 。
散列表分析
散列表是一种直接计算记录存放地址的方法,
它在关键码与存储位臵之间直接建立了映象 。
当选择的散列函数能够得到均匀的地址分布时,在搜索过程中可以不做多次探查。
由于很难避免冲突,增加了搜索时间。 冲突的出现,与 散列函数的选取 (地址分布是否均匀 ),处理冲突的方法 (是否产生堆积 ) 有关。
在实际应用中使用关键码进行散列时,如在用作关键码的许多标识符具有相同的前缀或后缀,或者是 相同字符的不同排列 的场合，
不同的散列函数往往导致散列表具有不同的搜索性能 。
下图给出一些实验结果。
= n / m 0,5 0 0,7 5 0,9 0 0,9 5
散列函数种类开散列法闭散列法开散列法闭散列法开散列法闭散列法开散列法闭散列法平平 方方 取取 中中 11,,22 66 11,,77 33 11,,44 00 99,,77 55 11,,44 55 33 11 00,,11 44 11,,44 77 33 11 00,,55 33
除留余数 1,1 9 4,5 2 1,3 1 1 0,2 0 1,3 8 2 2,4 2 1,4 1 2 5,7 9
移位折叠 1,3 3 2 1,7 5 1,4 8 6 5,1 0 1,4 0 7 1 0,0 1 1,5 1 1 1 8,5 7
分界折叠 1,3 9 2 2,9 7 1,5 7 4 8,7 0 1,5 5 6 9,6 3 1,5 1 9 1 0,5 6
数字分析 1,3 5 4,5 5 1,4 9 3 0,6 2 1,5 2 8 9,2 0 1,5 2 1 2 5,5 9
理论值 1,2 5 1,5 0 1,3 7 2,5 0 1,4 5 5,5 0 1,4 8 1 0,5 0
搜索关键码时所需对桶的平均访问次数从图中可以看出,开散列法优于闭散列法 ；
在散列函数中,用除留余数法作散列函数优于其它类型的散列函数,最差的是折叠法。
当装填因子?较高时,选择的散列函数不同,散列表的搜索性能差别很大。在一般情况下多选用除留余数法,其中的除数在实用上应选择不含有 20以下的质因数的质数。
对散列表技术进行的实验评估表明,它 具有很好的平均性能,优于一些传统的技术,如平衡树 。但散列表 在最坏情况下性能很不好 。
如果对一 个有 n 个关键码的散列表执行一次搜索或插入操作，最坏情况下需要 O(n)
的时间。
Knuth对不同的冲突处理方法进行了概率分析。
若设? 是散列表的装填因子：
用地址分布均匀的散列函数 Hash( )计算桶号。
Sn 是搜索一个随机选择的关键码 xi (1? i? n)
所需的关键码比较次数的期望值
Un 是在长度为 m 的散列表中 n 个桶已装入表项的情况下，装入第 n+1 项所需执行的关键码比较次数期望值 。
前者称为在? = n / m 时的搜索成功的平均搜索长度，后者称为在?= n / m时的搜索不成功的平均搜索长度。
m
n
表中预设的最大记录数表中已装有记录数?
用不同的方法溢出处理冲突时散列表的平均搜索长度如图所示。
平 均 搜 索 长 度 ASL
处 理 冲 突的 方 法搜索成功
Sn
搜索不成功 Un
( 登入新记录 )
闭散线性探查法
)(
列法伪随机探查法二次探查法双散列法
1l o g
1
e
开 散 列 法
( 同义词子表法 )
e
散列表的装填因子? 表明了表中的装满程度 。 越大,说明表越满,再插入新元素时发生冲突的可能性就越大 。
散列表的搜索性能,即 平均搜索长度 依赖于散列表的装填因子,不直接依赖于 n 或 m。
不论表的长度有多大,我们总能选择一个合适的装填因子,以把平均搜索长度限制在一定范围内 。
例 求散列表大小并设计散列函数
设有一个含 200个表项的散列表，用二次探查法解决冲突，按关键码查询时找到一个新表项插入位臵的平均探查次数不超过 1.5，则散列表项应能够至少容纳多少个表项。再设计散列函数 （设搜索不成功的平均搜索长度为
Un＝ 1 / (1 -α),其中 α为装填因子）
解答：设表中表项个数 n = 200，搜索不成功的平均搜索长度
Un＝ 1 / (1 -α)? 1.5 1/3
n / m = 200 / m = 1/3 m? 600
可扩充散列
可扩充散列是一种动态散列方法，它对传统的散列技术进行了扩充，使之能够动态地适应对文件存储容量的需求，并能保持高效的搜索效率。
二叉 Trie树
若设每一个关键码由 2个字符组成,而每一个字符用 3 个二进位表示。则有标识符 A0 A1 B0 B1 C0 C1 C2 C3
二进位 100 100 101 101 110 110 110 110
表示 000 001 000 001 000 001 010 011
假设把这些关键码放到有 4 个页块 的文件中,
每页最多可以容纳 2 个关键码,各页可通过
2 个二进位 00,01,10,11 加以索引。现在利用各关键码的最低 2 位来决定它应放到哪个页块上。
A0,B0 C2 C3
0
0 1 0 1
1
基于 4个页块的 2层索引
A1,B1
一般地,根据各关键码的二进位表示,从最低位到最高位进行划分,各页块的索引构成一个二叉树结构 。这就是 二叉 Trie树 。
首先,在根结点处按各关键码的最低位是 1
还是 0,划分为两组。 对于每一组再按次低位是 1 还是 0 继续分组,如此分下去,直到每组剩下不多于 2 个关键码为止。
因此，在二叉 Trie树中有两类结点,分支结点 和 叶结点 。 分支结点 按其相关二进位是 1
还是 0,分为两个方向 ; 仅在 叶结点 包含指向关键码存放页块的指针 。
A0,B0 C2 C3
0
0 1 0 1
1
A1,B1 C5
0 1
插入新的关键码 C5 时,因为 C5 的二进制表示 110101的最低两位二进位是 01,所以应把它放到 A1,B1所在的 第 3页中。但是此时该页块已满,发生了溢出。为此,将 第 3页 扩充一倍，一页分裂为两页。
再插入一个新关键码 C1,它应插入到 A1,B1
所在的页块中。这时又发生溢出,需要再分裂 A1,B1 所在页块：根据 A1,B1,C1 的最低 4 位将它们重新分配到这两个页块中。
A0,B0 C2 C3
0
0 1 0 1
1
C5
0 1
B1
0 1
A1,C1
以上两个插入结果降低了树搜索效率 。 为解决上述问题,1979年 Fagin等人提出了可扩充散列方法 。
该方法采用一种特殊的散列函数,把关键码转换成二进制数字表示的伪随机数集合,取其最低若干位作为页块地址,从而避免了关键码的不均匀分布 。 并且把 二叉 Trie树映射为目录表,以避开在二叉 Trie树中的长时间搜索过程 。
利用可扩充散列技术组织的文件叫做散列文件。
若设有 n 个记录,每个记录有一个关键码域用以唯一标识这个记录。又设每个页块有 p 个记录,整个文件有 m 个页块,则散列文件的存储利用率可用 n/(m*p) 来度量。
从上面的例子可知，存在着两个问题：
对某个页块的访问时间取决于区分关键码所需的二进位数。
如果关键码的分布不均匀，最后产生的二叉 Trie树是倾斜的。
将二叉 Trie树转换为目录表
为将二叉 Trie树转换为目录表,首先需要将二叉 Trie树的分支结点部分 (索引部分 ) 转换为一棵满二叉树 ——即所有指向叶结点的分支结点都位于同一层次上。然后 再把这棵二叉树映射为指示各个页块的目录表 。
一般地,目录表由一组指向页块的指针组成 。 如果区分所有的关键码需要 k 位二进制数,则 目录项个数应为 2k,其编址为 0 到
2k -1。
A0,B0 C2 C3
0
0 1 0 1
1
A1,B1 C5
0 1 0 10 1 0 1
A0,B0 C2 C5A1,B1 C3
000 001 010 011 100 101 110 111目录满二叉树 反向读页地址正向读页地址
一般使用 关键码的最后 k 个二进位 作为 目录项下标 来搜寻该关键码所在页块的指针,
然后对这个页块进行搜索。
A0,B0 C2A1,B1 C3
00 01 10 11
上面的目录由 4 个目录项组成,其编址从 0
到 3。 通过目录项的指针,可找到相应页块的地址,从而读取该页块的内容 。
目录或页块的 可区分编址位数 叫做其 深度 。
在目录表中插入一个新关键码后,其深度可能增加 1。为了保持最高搜索效率,需要压缩目录的深度,使其深度仍为 2。
由于有 5 个目录项,需要由最低 3 位来区分它们,为此，设臵 8个目录项，其下标从 0到 7。
这样，某些页块就有多个指针指向它。
C5C3
000 001 010 011 100 101 110 111
A0,B0 A1,B1 C2
使用目录表来表示一棵二叉 Trie树,允许关键码序列动态地增长和收缩 。
这里假设操作系统能够有效地为人们提供页块,并能够回收页块到可利用空间中去。
访问一个页块的步骤为：
利用散列函数找到目录项的地址；
按此地址检索相关的页块。
如果所有的关键码在各个页块中的分配不均衡,则目录表可能会增长得相当大,且多数指针指到同一个页块。为防止出现此种情况,
使用一个均匀分布的散列函数得到一个随机地址，用它作为二进位下标。
可扩充散列结构 由一组页块和一个目录表构成 。每一个页块包括的信息有
该页块的局部深度 PgDepth,它指明该页块中存放的对象的二进位地址的低位部分有多少位是相同的；
该页块关键码个数 Count和 存放关键码的数组 Names。页块都存储在文件中。
目录表由目录项组成。每个目录项是一个指示某一页块的地址的指针。一般用一个数组 Directory来存放它们，其下标范围从
0 到 MaxDir-1。 目录表深度为 DicDepth,
它指明为区分各个页块所需的二进位数 。
插入 C5,分裂 01
页,目录扩一倍
A0,B0 C2A1,B1 C3
00 01 10 11
DirDepth=2
PgDepth PgDepth PgDepth PgDepth
=2 =2 =2 =2
C5C3
000 001 010 011 100 101 110 111
A0,B0 A1,B1
DirDepth
=2
C2
PgDepth PgDepth PgDepth PgDepth PgDepth
=2 =3 =2 =2 =3
关键码插入及页块分裂
在向一个页块插入关键码 key 时,如果该页块不满,可以直接将关键码插入 ; 如果该页块已满,需要分裂页块。
若原来页块的 PgDepth=d,分裂后两个伙伴页块的二进制地址都增加一位,它们的局部深度 PgDepth=d+1。除了低阶共享的 d位外,
用最高阶的一位来区分它们。
在页块分裂后必须扩充目录表。让目录表的深度加 1，所有的目录项增加一倍,原来地址为的目录项中的页块指针分别放到 0和
1的两个目录项中。
C5
C3
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
B1
C2
A0,B0
A1,C1
DirDepth=4
PgDepth=2
PgDepth=4
PgDepth=2
PgDepth=2
PgDepth=3
PgDepth=4
如果目录项的二进制地址有 d 位,则整个目录表的深度 DicDepth = d,目录项个数 (表的长度 )有 2d 个。
DicDepth = log2(目录表中目录项个数 ) = 目录表的二进位数 。
有时有多个指针指向同一个页块,它表明该页块的局部深度小于目录表深度,
PgDepth < DicDepth
如果页块的 PgDepth = d'，则目录表中同时指向该页块的指针个数必为 2d-d'。
初始时 DicDepth=0,目录项个数 n = 2DicDepth
= 1,所有关键码都在同一个页块上。
关键码删除及页块合并
在执行关键码删除时,若 两个伙伴页块中的关键码个数总和少于或等于其中一个单独页块的容量时,就应把这两个页块合并成一个。
求二进制地址为 p 的某目录项所指页块的伙伴页块的方法：
若设目录项 p 所指页块的 PgDepth=d',把地址 p 的第 d' 位求反,得到一个新的二进制地址 p',地址为 p' 的目录项所指页块即为原页块的伙伴 页块。
页块中关键码减少可能会导致目录表的紧缩。
合并伙伴页块的工作包括：
将关键码合并到其中任一个页块中；
释放空闲的页块；
将原来的指针都指向合并后的页块。
如果目录中指向每一个页块的指针个数都大于或等于 2,即所有页块的 PgDepth < DicDepth
需要紧缩目录。其过程与目录扩充的过程相反。
性能分析
可扩充散列技术是一种非常好的问题解决方法,其 散列文件的地址空间可以扩充和收缩,
文件自身能够增长和缩小 。
在时间方面,用基于目录表的可扩充散列方法进行检索,仅需要 2次磁盘访问 。因为不存在溢出问题,访问时间与文件大小无关,时间开销达到 O(1)。
在空间方面,因增加不均匀分布的关键码可能会导致目录表扩充一倍，许多指针指到同一页块，这样会消耗许多存储空间。
在空间利用率方面评价散列技术的方式仍然用装载因子 α来衡量,
Fagin,Nievergelt等人做了一系列的试验和模拟。他们发现,可扩充散列的页块空间利用率在 0.53 到 0,94 之间周期性地变动。若给定的记录数为 r,一个页块可容纳 b 个记录,
则所需的平均页块数 N 和装载因子? 为：
表中最大可容纳记录 数表中已存储的记录数α?
Nb
r
2b
rN
ln?
