§ B-树 1.概念 B-树是一种完全平衡的多阶查找树，主要是作为磁盘文件的索引组织，用于外部查找。

Presentation on theme: "§ B-树 1.概念 B-树是一种完全平衡的多阶查找树，主要是作为磁盘文件的索引组织，用于外部查找。"— Presentation transcript:

1 § 9.3.2 B-树 1.概念 B-树是一种完全平衡的多阶查找树，主要是作为磁盘文件的索引组织，用于外部查找。
基本想法是增大结点来降低树高，减少访问外存的次数 一棵m阶B-树，每个结点最多有m个孩子，m一般为50－2000 例如，1棵1001阶B-树，3层即可包含10亿以上的Keys，当根结点置于内存时，查找任一Key至多只要访问2次外存。 1000 … 1001 1个结点 1000个关键字 1001个结点 1,001,000个关键字 1,002,001个结点 1,002,001,000个关键字

2 § 9.3.2 B-树 定义：一棵m(m≥3)阶的B-树是满足下述性质的m叉树： 性质1
每个结点至少包含下列数据域:(j, P0, K1, P1, K2, … , Kj , Pj ) j：keys总数， Ki：关键字， Pi：指针 keys(P0) < K1 <keys(P1) < K2 < … < Kj < keys(Pj) 性质2：所有叶子在同一层上，叶子层数为树高h，叶子中的指针为空。 性质3：每个非根结点中的关键字数目j满足： ⌈m/2⌉-1≤j≤m-1 即：每个非根的内部结点的子树数在⌈m/2⌉和m之间 性质4：非空的B－树中，根至少有1个关键字。 即：根不是叶子时，子树数为：2～m之间

3 § 9.3.2 B-树 2、运算 查找 多路查找：先在结点内查找（折半或顺序），后在子结点中查找（读盘） 插入和生成
平衡机制：满时插入分裂结点，从叶子 根，树高可能长 一层 删除 平衡机制：半满时删除，可能要合并结点，从叶子 根， 树高可能减一层

4 § 9.3.2 B-树 3、性能分析 树高 查找、插入、删除的时间为：读写盘O(h), CPU计算O(mh)，均与树高相关。
这里，t＝ ⌈m/2⌉，n为关键字总数。 因为lgn = (logtn)(lgt)，所以平衡的BST高约为B-树高的lgt倍 例如，m＝1024，lgt＝9。若B-树高为3，则平衡的BST高为27

5 • • • • • Ex.9.13, 9.14 B-树用于内存 为何m必须小？ 因为内存中计算时间为：
O( mh )＝O( mlogtn )＝O( mlgn/lgt )＝O( lgn( m/lgt ) ) ∵m/lgt>1, ∴令m＝3。 3阶B-树（2－3树） m=3, ⌈m/2⌉=2。即每个非叶结点或有2棵树、或有3棵树。 • • • • • Ex.9.13, 9.14

6 § 9.4 散列技术 lgn＋O(1) 要突破此界，就不能只依赖于比较来进行。 § 9.4.1 散列表的概念
上述查找均是基于key的比较，由判定树可证明，在平均和最坏情况下所需的比较次数的下界是： lgn＋O(1) 要突破此界，就不能只依赖于比较来进行。 § 散列表的概念 直接寻址：当结点的key和存储位置间建立某种关系时，无须比较即可找到结点的存储位置。 例如，若500个结点的keys取值为1～500间互不相同的整数，则keys可作为下标，将其存储到T[1..500]之中，寻址时间为O (1)。

7 § 9.4.1 散列表的概念 压缩映象 例子 设影像出租店 总片数：10,000张 借还：500人次/每天
记录：（电话号码，姓名，住址，…）, Key为7位电话号码 直接寻址：须保留1000万个记录 但实际只要大于500即可，最多1万个记录 一般情况 全集U：可能发生的关键字集合，即关键字的取值集合 实际发生集K：实际需要存储的关键字集合 ∵ |K| << |U|，当表T的规模取|U|浪费空间，有时甚至无法实现 ∴ T的规模一般取O(K), 但压缩存储后失去了直接寻址的功能

8 § 散列表的概念 散列（hash）函数h 在keys和表地址之间建立一个对应关系h，将全集U映射到T[0..m-1]的下标集上： h：U→{ 0, 1, … , m-1 } ∀ki∈U，h(ki) ∈ { 0,1,…,m-1 } 散列表: T 散列地址（散列值）：散列函数值h(ki) 散列（hashing）： 关键字 集合 存储地址 hash T[0..m-1] h(k2) U K k1 . k2 . k3. h(k1)=h(k3) m-1

9 § 9.4.1 散列表的概念 散列（hash）函数h(续) 冲突(碰撞): 若ki≠kj，有h(ki)＝h(kj)
能完全避免冲突吗？ 须满足：① |U|≤m ② 选择合适的hash函数 否则只能设计好的h使冲突尽可能少 解决冲突： 须确定处理冲突的方法 装填因子：冲突的频繁程度除了与h的好坏相关，还与表的填满程度相关 α＝n/m， 0≤ α ≤ 1

10 § 9.4.2 散列函数的构造方法 原则：简单、均匀 简单——计算快速，均匀——冲突最小化
假定：关键字定义在自然数集合上，否则将其转换到自然数集合上 1、平方取中法 先通过平方扩大相近数的差别，然后取中间的若干位作为散列地址。因为中间位和乘数的每一位相关，故产生的地址较为均匀。 int Hash( int k ) { k *=k; k /=100; //去掉末尾两位数 return k％1000；//取中间3位，T的地址为0~999 }

11 § 9.4.2 散列函数的构造方法 2、除余法 3、随机数法 选取哈希函数考虑的因素 用表长除以关键字，取其余数作为散列地址
h(k)＝ k%p； p≤m，有时取p＝m p最好取素数，或取不包含小于20的质因数的合数 优点：最简单，无需定义为函数，直接写到程序里使用 3、随机数法 h(k)＝random( k ); 伪随机函数须保证函数值在0～m-1之间 选取哈希函数考虑的因素 计算哈希函数所需时间 关键字长度 哈希表长度（哈希地址范围） 关键字分布情况 记录的查找频率

12 § 处理冲突的方法 1、开放地址法（闭散列） 基本思想：当发生冲突时，使用某种探测技术在散列表中形成一个探测序列，沿此序列逐个单元查找，直到找到给定的key，或碰到1个开放地址（空单元）为止 插入时，探测到开地址可将新结点插入其中 查找时，探测到开地址表示查找失败 开地址表示：与应用相关，如key为串时，用空串表示开地址 一般形式 hi＝（h(k)＋di）％m ≤i ≤ m－1 （9.1） 探测序列：h(k)(相对于i=0, 即h0), h1, h2 , …, hm-1 开地址法要求：α<1， 实用中 0.5≤ α ≤ 0.9

13 § 9.4.3 处理冲突的方法 （1）线性探测法 开放地址法分类：按照形成探测序列的方法不同，可将其分为3类：线性探测、二次探测、双重散列法
基本思想：将T[0..m-1]看作一循环向量，令di＝i，即 hi＝（h(k)＋i）％m ≤i ≤ m－1 若令d＝h(k)，则最长的探测序列为： d,d+1,…,m-1,0,1,…,d-1 探测过程终止于 探测到空单元：查找时失败，插入时写入 探测到含有k的单元：查找时成功，插入时失败 探测到T[d-1] 但未出现上述2种情况：查找、插入均失败

14 § 处理冲突的方法 例1：已知一组keys为（26,36,41,38,44,15,68,12,06,51）, 用除余法和线性探测法构造散列表 解：∵ α<1，n＝10，不妨取m＝13，此时α≈0.77 h( k )= k% keys：(26,36,41,38,44,15,68,12,06,51) 对应的散列地址：( 0,10, 2, 12, 5, 2, 3, 12, 6, 12) 12 11 10 9 8 7 6 5 4 3 2 1 38 36 44 41 26 51 06 68 15 T[0..12] 探测次数

15 聚集增加了探测序列的长度，使查找时间增加。应跳跃式地散列。
非同义词冲突：上例中，h(15)=2，h(68)=3，15和68不是同义词，但是15和41这两个同义词处理过程中，15先占用了T[3]，导致插入68时发生了非同义词的冲突。 聚集（堆积）：一般地，用线性探测法解决冲突时，当表中i,i+1,…,i+k的位置上已有结点时，一个散列地址为i,i+1,…,i+k,i+k+1的结点都将争夺同一地址：i＋k＋1。这种不同地址的结点争夺同一后继地址的现象称为聚集。 聚集增加了探测序列的长度，使查找时间增加。应跳跃式地散列。 12 11 10 9 8 7 6 5 4 3 2 1 38 36 44 41 26 51 06 68 15 T[0..12] 探测次数

16 § 9.4.3 处理冲突的方法 （2）二次探测法 探测序列为( 增量序列为di =i2 )：
hi＝（h(k)＋i*i）％m ≤i ≤ m－1 缺点：不易探测到整个空间 （3）双重散列法 是开地址法中最好的方法之一，探测序列为 hi＝（h(k)＋i* h1(k) ）％m ≤i ≤ m－1 即： di =i* h1(k) 特点：使用了两个散列函数，一般须使h1(k)的值与m互素

17 § 处理冲突的方法 2、拉链法（开散列） 基本思想：将所有keys为同义词的结点连接在同一个单链表中，若散列地址空间为0～m-1，则将表定义为m个头指针组成的指针数组T[0..m-1]，其初值为空。 例2：keys和hash函数同前例 44 ^ 41 15 26 68 06 36 12 38 51 比较次数：

18 § 9.4.3 处理冲突的方法 2、拉链法（续） 特点 无堆积现象、非同义词不会冲突、ASL较短 无法预先确定表长度时，可选此方法
删除操作易于实现，开地址方法只能做删除标记 允许α>1，当n较大时，节省空间

19 § 9.4.4 散列表上的运算 仅给出开放定址法处理冲突时的相关运算 存储结构 #define NIL -1 //空结点标记
#define m 997 //表长，依赖应用和α typedef struct { KeyType key; //…. }NodeType, HashTable[m]; 1、查找运算 和建表类似，使用的函数和处理冲突的方法应与建表一致 开地址可统一处理

20 § 9.4.4 散列表上的运算 int Hash( KeyType K, int i){
return ( h(K)+ Increment( i ) )%m; //Increment相当于9.1式中的di, 返回hi } Int HashSearch( HashTable T, KeyType K, int *pos){ int i=0; //探测次数计数器 do { *pos=Hash( K, i ); //求探测地址hi if ( T[*pos].key==K ) return 1; //查找成功 if ( T[*pos].key==NIL ) return 0; //查找失败 } while (++i<m); //最多探测m次 return -1; //表满且未找到，失败

21 § 9.4.4 散列表上的运算 2、插入和建表 插入：先查找，找到开地址成功，否则(表满、K存在)失败
void HashInsert( HashTable T, NodeType new ){ int pos, sign; sign=HashSearch( T, new.key, &pos ) ; if ( !sign ) //标记为0，是开地址 T[pos]=new; //插入成功 else if ( sign>0 ) printf(“duplicate key”) ; //重复，插入失败 else Error(“overflow”); //表满，插入失败 } 建表：将表中keys清空，然后依次调用插入算法插入结点

22 § 9.4.4 散列表上的运算 3、删除 开地址法不能真正删除（置空），而应该置特定标记Deleted
当有删除操作时，一般不用开地址法，而用拉链法 4、性能分析 只分析查找时间，插删取决于查找，因为冲突，仍需比较。 实例分析（见例1和例2图） 等概率假设

23 成功 线性探测：ASL＝(1*6+2*2+3*1+9*1)/10=2.2 //n=10
12 11 10 9 8 7 6 5 4 3 2 1 38 36 51 06 44 68 15 41 26 T[0..12] 探测次数 44 ^ 41 15 26 68 06 36 12 38 51 比较次数：

24 § 9.4.4 散列表上的运算 不成功 线性探测：直到探测到开地址为止
ASL＝( )/13=4.54 //m=13 注意：当m>p（p＝|散列地址集|）时，分母应该为p 拉链法：不包括空指针判定 ASL＝( )/13=0.77 //m=13 T[0..12] 12 11 10 9 8 7 6 5 4 3 2 1 38 36 51 06 44 68 15 41 26 探测次数

25 § 9.4.4 散列表上的运算 不成功(续) 拉链法：不包括空指针判定
ASL＝( )/13=0.77 //m=13 44 ^ 41 15 26 68 06 36 12 38 51 比较次数：

26 § 9.4.4 散列表上的运算 一般情况 线性探测 成功：ASL＝（1＋1/(1－α)）/2 失败：ASL＝（1＋1/(1－α)2）/2
显然，只与α相关，只要α合适，ASL＝O(1)。 其他方法优于线性探测：略 5、用途 加速查找 加密等信息安全领域 Ex. 9.19，9.45