Tips
大部分内容就是数据结构中哈希表的内容，结合数据结构和数据库的实现好理解很多。
1. 数据结构
DBMS对系统内部的许多不同部分使用各种数据结构：
- Internal Meta-Data（内部元数据）：跟踪有关数据库和系统状态的信息。
- Core Data Storage （核心数据存储）：可用作数据库中元组的基本存储。
- Temporary Data Structures（临时数据结构）：DBMS可以在处理查询时动态构建数据结构，以加快执行速度(例如，用于 joins 的哈希表)。
- Table Indexes（表索引）：辅助数据结构，使查找特定元组更容易。
设计决策：
- 数据组织：我们如何布局内存以及在数据结构中存储哪些信息。
- 并发性：如何让多线程不出问题地访问数据结构。
2. 哈希表
哈希表实现了将 key 映射到 value 的关联数组抽象数据类型。它提供了平均O(1)的计算复杂度（时间）和O(n)的存储复杂度（空间）。
哈希表实现由两部分组成：
- 哈希函数：如何将大的密钥空间映射到较小的域中。它用于计算存储桶或槽数组的索引。需要考虑快速执行和冲突率之间的权衡。
- 哈希方案：如何处理散列后的密钥冲突。需要考虑分配大型哈希表以减少冲突与执行额外指令以查找/插入键之间的权衡。
3. 哈希函数
哈希函数接受任何 key 作为其输入。然后，它返回该 key 的整数表示(即,“hash”)。函数的输出是确定性的(即，相同的键应该始终生成相同的散列输出)。
DBMS不想使用密码散列函数(例如，SHA-256)，因为我们不需要担心保护密钥的内容。这些散列函数主要由DBMS内部使用，因此信息不会泄漏到系统之外。对于本课，我们只关心散列函数的速度和冲突率。目前最先进的散列函数是Facebook XXHash3。
Tips1:
加密常见Hash:
- SHA-256
- MD5(2004年被山大王小云老师破解)
数据库常见Hash：
- CRC-64(1975)
- MurmurHash(2008)
- Google CityHash(2011)
- Facebook XXHash(2012)
- Google FarmHash(2014)
Tips2:
不要自己写哈希，浪费时间，直接拿来用
4. 静态（Static）哈希方案
静态哈希方案是其中哈希表的大小是固定的方案。这意味着如果DBMS耗尽了哈希表中的存储空间，则它必须使用更大的表从头开始重建它。通常，新哈希表的大小是原始哈希表的2倍。（我们已知哈希表的大小，且不动态增长。）
为了减少浪费比较的次数，重要的是要避免碰撞×散列key。这需要具有两倍于预期元素数量的段数的哈希表。
4.1. Linear Probe Hashing
线性探针哈希，这是最基本的 hashing 方案。它通常也是最快的。它使用单一的槽表。哈希函数允许DBMS快速跳转到 slots 并查找所需的 key 。（其实就是开放地址法）
- 通过线性搜索表中的下一个空闲插槽来解决冲突；
- 要查看值是否存在，请使用散列转到 slot ，并扫描 key 。如果找到所需的 key 或遇到空 slot ，扫描将停止。
删除时添加⼀个tombstone(墓碑)标记
4.2. Robin Hood Hashing
这是线性探测散列的扩展，它寻求减少每个 key 从它们在哈希表中的最佳位置的最大距离。允许线程从“rich”keys 中窃取slot，并将它们分配给“poor”keys。
- 每个 key 跟踪它们在表中从其最佳位置开始的位置的数量。
- 插入时，如果第一个 key 比第二个 key 离其最佳位置的距离更远，则一个 key 将占据另一个 key 的槽。然后，必须将删除的 key 重新插入到表中。
4.3. Cuckoo Hashing
这种方法不是使用单个哈希表，而是使用不同的哈希函数维护多个哈希表。哈希函数是相同的算法(例如，XXHash、CityHash)；它们通过使用不同的 seeds 为相同的 key 生成不同的哈希。
- 在插入时，检查每一张表，并挑选任何有空位的 slot 。
- 如果没有表有空闲的 slot ，则从其中一个表中取出元素，并对其进行重新 hash 以找到新的位置。
- 如果我们找到一个循环，那么我们可以用新的hash函数 seeds 重建所有hash表(不太常见)，或者使用更大的表重建hash表(更常见)。
5. 动态（Dynamic）哈希方案
静态散列方案要求DBMS知道它想要存储的元素的数量n。否则，如果需要增大/缩小大小，它将重新构建该表。
动态哈希方案能够按需调整哈希表的大小，而无需重新构建整个表。这些方案以不同的方式执行调整大小的操作，这些方式可以最大化读取或写入。
5.1. 链式哈希 Chained Hashing
这是最常见的动态散列方案。DBMS为哈希表中的每个 slot 维护 桶buckets 的链接列表。
- 通过将具有相同hash key 的元素放入同一 buckets 来解决冲突。
- 如果 buckets 已满，则向链中添加另一个buckets 。哈希表可以无限增长，因为DBMS不断添加新的 buckets 。
5.2. 可扩展哈希 Extendible Hashing
链式散列的改进变体，它拆分 buckets ，而不是让链永远增长。该方法允许哈希表中的多个槽位置指向相同的桶链。
重新平衡哈希表背后的核心思想是在拆分时移动 buckets 条目，并增加要检查以在哈希表中查找条目的 bits 数。这意味着DBMS只需在拆分链的 buckets 内移动数据；所有其他 buckets 保持不变。
- DBMS维护全局和局部深度 bit 计数，以确定在槽数组中查找桶所需的 bit 数。
- 当 buckets 满时，DBMS拆分 buckets 并重新洗牌其元素。如果拆分 buckets 的局部深度小于全局深度，则新buckets 只是添加到现有槽数组中。否则，DBMS会将槽数组的大小增加一倍以容纳新的 buckets ，并递增全局深度计数器。
5.3. 线性哈希 Linear Hashing
该方案不是在桶溢出时立即拆分桶，而是维护一个拆分指针来跟踪下一个要拆分的桶。无论该指针是否指向溢出的桶，DBMS总是拆分。溢出标准由实现决定。
- 当任何桶溢出时，通过添加新的槽条目在指针位置拆分桶，并创建新的散列函数。
- 如果散列函数映射到先前由指针指向的槽，则应用新的散列函数。
- 当指针到达最后一个槽时，删除原有的散列函数，代之以新的散列函数。
