1. Data Structure
DBMS 主要包括以下几种数据
-
Internal Meta-Data : 记录有关数据库和系统的信息
-
Core Data Storage : 记录 tuple 的信息
-
Temporary Data Structures
-
Table Indices
主要考虑以下两个问题
-
数据组织
-
数据的可靠性
2. Hash Table
Hash Function
-
将值转化为一个较小的键
-
在 速度 和 碰撞率 之间进行权衡。
Hashing Scheme
-
该如何处置碰撞的情形
-
需要在 哈希表大小 与 额外信息维护之间 权衡
3. Hash Function
不管输入的 key 是什么,输出一个 特别的 数字 的函数。
4. Static Hashing Schemes
4.1 Linear Probe Hashing
线性探针
我们解决哈希冲突的方法是,如果我们的哈希函数返回的位置已经被占用了,那么则一直向下取一个位置,直到找到表中空的值。
在删除操作中,可能会出现一种情形,有的值并不是 hash function 产生的直接值,而是通过一直取下一个位置得到的值。
在这种情形下,我们所采取的方法有。
-
将受到偏移影响的值往回调整。通过重新哈希的方式进行调整。效率比较低下。
-
将那些删除了的值标记为已删除。这些值可以在新的值需要使用的时候重新利用。不过需要周期性的垃圾回收。
存储相同的值
存储相同的 key 但有不同的 value 的值的时候,我们可以有两种办法解决。
-
对于每个 key 他们的 value 开辟出来一个单独的空间
-
所有的 key 都用 哈希函数 散列在一个存储空间中。
4.2 Robin Hood Hashing
这是线性探针算法的一个升级版,旨在解决分布不均的问题。在上面的算法中,可能存在一些 key,经过哈希计算后可能会聚集在一块导致哈希算法劣化。 Robin Hood hashing 解决冲突的方式会将部分 rich 的 key 分配给 poor key.
这种避免哈希碰撞的方法是,给每个值都记录一个偏移值,表中的每个值在向下搜索的时候,需要和表中的值进行对比。如果当前偏移值比表中值的偏移值大,那么则将当前值和表中值进行替换。直到找到空位结束。
1 | void Robin_hood_Hashing(int key) { |
4.3 Cuckoo Hashing
这种解决碰撞的方法是使用两种哈希函数和两张哈希表完成的。
对于输入的 key 他会计算出 val[0]
和 val[1]
在不确定的情况下,会随机采用其中一个作为最终的结果,当其中一个触发冲突的时候,则采用一个哈希函数与哈希表。如果两个都冲突的话,那么则重新计算冲突的哈希,直到没有冲突。
采用这正方法,在查询的时候复杂度永远都是 $O(1)$ ,但插入的代价比加大。
5 Dynamic Hashing Schemes
以上的的哈希表都基于固定大小的元素,所以需要一些动态的哈希表。
5.1 Chained Hashing
对每个哈希值都维护一 个链表。将所有哈希值相同的键都放在一个 bucket 中。bucket 是通过链表的形式连接在一起的。
5.2 Extendible Hashing
在 bucket 快 满的时候,通过二进制前缀开辟新的 bucket。
5.3 Linear Hashing
运行时动态扩容的一种哈希。