-
Notifications
You must be signed in to change notification settings - Fork 32
/
4、散列索引结构.md
94 lines (48 loc) · 4.53 KB
/
4、散列索引结构.md
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#### 实现：散列索引
**散列**
* 有M个桶，每个桶是有相同容量的存储块(可以是内存页，也可以是磁盘块)
* 内存数据可采用散列确定存储页，主文件可采用散列确定存储块，索引亦可采用散列确定索引项的存储块
* Ｍ个桶。一个桶可以是一个存储块，亦可是若干个连续的存储块。
* 散列函数 h(k)，可以将键值k映射到 {0,1,...,M-1}中的某一个值
* 将具有键值k的记录Record(k)存储在对应h(k)编号的桶中
* 在键值几倍于桶的数目时，每个散列值都可能多于一个桶，形成一个主桶和多个溢出桶的列表，此时需要二次检索：先散列找到主桶号，再依据链表逐一找到每个溢出桶。
<img src="https://img-blog.csdnimg.cn/20201127133547489.png" width="50%" height="50%" />
* 散列索引的好处，还可以进行集合运算，即对每个桶进行集合运算
**桶的数目M**
* 固定值----静态散列索引
* 如果桶的数目M不变：M过大，则浪费；M过小，则将产生更多的溢出桶，增加散列索引检索的时间。
* 桶的数目随键值增多，动态增加----动态散列索引
* 可扩展散列索引
* 线性散列索引
**动态散列索引---可扩展散列索引**
* 实现
* 为桶引入一间接层，即用一个指向块的指针数组来表示桶，而不是用数据块本身组成的数组来表示桶
* 指针数组能增长，其长度总是2的幂。因而数组每增长一次，桶的数目就翻倍。不过，并非每个桶都有一个数据块；如果某些桶中的所有记录可以放在一个块中，则这些桶可能共享一个块。
* 散列函数h为每个键计算出一个K位二进制序列，该K足够大，比如32。但是桶的数目总是使用从序列第一位或最后一位算起的若干位，此位数小于K,比如说i位。也就是说，当i是使用的位数时，桶数组将有2i个项。
* 示例
起始状态，只使用 hash 后值的 1 比特，那么只有 0、1 两种取值可以标记两个桶：
试图插入hash值为1111的数据时，第一位为1，所以插入第二个数据块，但里面满了，所以需要分裂成两个数据块，并且把位数 i 加一
* 如何扩容：分裂是把hash桶个数翻倍，其每个桶的索引都 *2 与 *2 + 1，即右边补 0 与 补 1
* rehash 哪部分：只 rehash 分裂的桶，没有分裂的桶，其中间层的两个指针都指向没分裂的桶
* 如何查找：下次决定使用哪个桶时，就使用的当前 i 的前 i 位正常查找即可。
* 存在问题
* 当桶数组需要翻倍时，要做大量的工作(当i很大时)；
* 当桶数翻倍后，其中间层的指针数组可能在主存中可能就装不下了，或者要占用更大的空间
* 如果每块的记录数很少，那么很有可能某一块的分裂比在逻辑上需要的分裂时间提前很多。
**动态散列索引---线性散列索引**
* 实现
* 桶数n的选择总是使 存储块的个数和记录总数 成一个固定的比例，例如80%。超过此比例，则桶数增长1块，分裂。
* 存储块并不总是可以分裂，所以允许有溢出块，尽管每个桶的平均溢出块数远小于1。
* 线性hash和可扩展hash思路一脉相承，但位数是从散列函数得到的位序列的右端(即低位)开始取。
* 示例（ i 表示使用hash值中多少位、n表示桶的数量、r表示记录的数量、假设拥挤阈值为1.7）
初始状态：
试图插入1010，比例大于阈值，导致过度拥挤，此时添加一个桶，多使用hash值中的1位：
* 如何扩容：每次在当前个数的基础上新增一个桶即可
* rehash 哪些：每次增加只是改变一位，所以只有rehash 没改变前所对应的那个桶即可。比如 增加了 10，是把 00 的 0 变为 1了，所以只 rehash 00 即可
* 如何查找：分类，m小于n时就是第m个块，否则是第（m - pow(2, i - 1)）块。比如找11的话，就是 11 - 10 = 01，找01那个桶。
继续插入元素0001，块满了但整体拥挤程度不超过阈值，所以拉链：
