Lecture #07: Hash Tables
1. Data Structures
- DBMS为系统内部的许多不同部分使用各种数据结构。例子如下：
- Internal Meta-Data:
用来跟踪数据库和系统状态信息的数据。 - Core Data Storage:
数据结构被用来作为数据库中tuple的基础存储。 - Temporary Data Structures:
DBMS可以在处理查询的同事建立数据结构以加快执行速度。（如：用于链接的哈希表） - Table Indices:
辅助数据结构使其更容易找到特定的tuple
- Internal Meta-Data:
- 在为DBMS实现数据结构的时候，有两个主要的设计决定需要考虑。
- Data Organization：
我们需要弄清楚如何布局内存，以及在数据结构内存储哪些信息，以便高效访问。 - Concurrency：
我们还需要考虑如何使多个线程访问数据结构而不造成问题。
- Data Organization：
2. Hash Table
-
哈希表实现了一个关联数组的抽象数据类型，将key映射到value。提供了平均\(O(1)\)的操作复杂度, 最坏为\(O(n)\) ，以及\(O(n)\)的存储复杂度。当然也需要优化
哈希表的实现包含2部分：
- Hash Function：
trade off -> fast execution & collision - Hashing Scheme：
如何处理collisions？
trade off -> memory allocate & execute additional instructions
- Hash Function：
3. Hash Functions
- 输进去一个key，出来一个代表这个key的整数。函数的输出是确定的。
- 数据库用到的哈希函数不需要那么复杂，因为我们不需要担心保护这些key。而且这些函数主要由DBMS内部使用，因此信息不会泄露到系统之外。一般来说，关心哈希函数速度和collision就行了。
4. Static Hashing Schemes
-
静态散列方案是指散列表的大小是固定的。即：如果DBMS哈希表存储空间用完了，就必须从头开始重建一个更大的哈希表。通畅为原大小的两倍。
-
为了减小空间浪费，避免collisions很重要。一般我们都设置为期望存放key的大小的两倍容量。
- The number of elements is known ahead of time.
- Keys are unique
- There exists a perfect hash function.
因此我们需要适当的选择哈希函数和哈希模式
4.1 Linear Probe Hashing
- 最基础的哈希策略，也叫开放地址法。太简单了这里省略不翻译了。
- 删除元素需要一定的技巧。因为如果是简单删除，然后将下面的移上一位的话，如果是循环表，可能会让上面的hash元素失效。
解决方案：- tombstones：墓碑法，标记这里删除了。缺点是浪费空间
- 删除元素后面相邻的移动一位，去填满删除的元素。但要注意，移动的entry必须是原来移动过的，才不会导致前面的hash失效。这种方法一般不会用。
- Non-unique Keys:
同样的key可能对应很多value的时候的方法：- Seperate Linked List: 链表存储
- Redundant Keys:更常见的方法，在表中多次存储一个键，用线性探测法
4.2 Robin Hood Hashing
- 线性探测法的扩展。旨在减少每个key与它们在哈希表中的最佳位置的最大距离。即，从更rich的key中偷取slot，并交给poor的key。
- 在这个策略中，每个条目也记录了它们与最佳位置的距离，每次插入的时候，如果被插入的key与它们在当前位置的最佳位置的距离，比当前条目的距离更远，就替换当前条目，并继续尝试在表中的更远位置插入旧条目。
- 例子：
参考原PPT
4.3 Cuckoo Hashing
- 维持多个哈希表。来调整key
- 例子：
参考原PPT
5. Dynamic Hashing Schemes
- 静态哈希不能调整大小，不太行。所以才DBMS一般都用动态哈希。可以rebuild表，如果需要grow / shrink size。
5.1 Chained Hashing
- 常用的结构。直接用链表。
5.2 Extendible Hashing
- 这个结构在Project-1中有。做完项目后体会更深刻。
- 详细请参考：extendible hashing
5.3 Linear Hashing
- 当一个桶溢出的时候，这个方案并不立刻分割，而是保持一个分割指针，跟踪下一个要分割的桶。无论这个指针是否指向一个溢出的桶，DBMS都会进行分割。溢出的标准由设计者决定。感觉跟Extendible Hashing的操作挺像的。
- 例子：
图太多懒得截图了。
参考原PPT