前面的文章已经介绍了磁盘管理和内存缓冲池管理的内容。接下来继续下一层介绍接入方式的内容。存取方法主要介绍一些数据结构，如HashTable和Tree。这些数据结构可以作为表的索引，也可以作为sql计算时的一些临时数据结构。在设计和使用这些数据结构时，需要注意两个问题。一是数据的组织，内存或磁盘中的数据如何组织，如何高效访问；另一个是数据结构的并发访问，在多线程环境下需要保证数据安全。今天，我们就来了解一下在数据库中经常使用，在数据结构中经常涉及到的哈希表。HashTable概念HashTable是一种无序的键值映射实现，它使用哈希函数计算数据在数组（槽）中的存储位置，平均而言，可以在O(1)时间内访问元素。如下图所示，我们使用哈希函数计算出key在数组中的下标，然后key对应到一个特定的值。在查找数据的时候，还需要计算hash值，然后定位key所在的位置，得到value。哈希函数从前面的描述可以看出，哈希函数在哈希表中的作用是非常重要的。哈希函数可以将任何类型的键转换成表示键的整数。理想情况下，我们希望哈希函数对任何不同的键计算出的值都是不同的，但在实际的哈希函数实践中，这几乎是不可能的。如果不同的键通过哈希函数计算出的值相同，这种情况称为哈希冲突（conflict），也称为哈希冲突（collision）。一般来说，哈希的计算速度越快，哈希碰撞的概率就越大，反之亦然，这需要在实际设计中进行权衡。数据库中常见的哈希函数实现包括：crc64：https://create.stephan-brumme.com/crc32/MurmurHash：https://github.com/aappleby/smhasherGoogleCityHash：https://github.com/google/cityhashFacebookXXHash:http://cyan4973.github.io/xxHash/GoogleFarmHash:https://github.com/google/farmhashStaticHashScheme接下来我们看一下静态哈希的几种实现方式，即所谓的Static，一般表示hash表的容量是固定的，所以可以存储的数据上限也是确定的，实际用的不多，可以作为参考。LinearProbeHash线性探针（LinearProbe）是一种比较直观简洁的HashTable实现。基本思路是，如果映射后的key存储位置已经被占用，则依次遍历数组，直到找到空闲位置插入数据。如下，新插入的数据E经过计算后，其位置在A的位置。但是A处已经有数据，此时发生冲突，所以会向后遍历，之后再找空闲的位置D插入。删除的逻辑类似。它还通过哈希函数计算出key的位置，然后找到对应的数据并删除。如果key不在原来的位置，需要像插入一样遍历，直到找到目标key。一般有两种删除方式。一种是直接在被删除的位置设置一个墓碑值，表示已经被删除。另一种是移动其他元素来填充删除的位置。这种方法不常用。对于重复键哈希表中的重复键，一般有两种处理方式。一种是通过值链表将同一个键的多个元素串联起来。这种方法比较简单直观。另一种方法是重复存储，把每个key看成是独立的，插入方法和上面介绍的完全一样。RobinHoodHashrobinhood哈希类似于线性探测，但有一些改进。它会记录每个key与其原始hash映射位置的距离，比如下图中的A，因为插入前没有数据，没有hash冲突，所以A记录的距离为0。如果此时插入数据C，如果C映射的位置也是A，就会发生hash冲突，所以向下检测一位，将C插入到A之后的位置。此时C与C的距离其原始映射位置为1。当插入新的key时，如果发生冲突，则继续向后检测，比较映射距离的值。如果新插入的键的距离大于该位置的值，则插入新的键。比如上面的例子，如果新插入的E映射到A的位置，那么E的距离为0，等于A的距离，继续往下。此时E的距离为1，等于C，然后继续。此时E变为2，大于D的距离1，所以E插入到D的位置，D移动到下一个空闲位置。CuckooHashcuckoohash使用多个哈希表，每个哈希表使用不同种子（随机种子）的哈希函数。插入数据时，每个哈希函数依次为key计算哈希值，如果对应的哈希表有空闲空间，则直接插入。例如，在下面的示例中，使用了两个哈希表。插入keyA时，计算两个哈希值，如果发现第一个哈希表空闲，则直接将数据插入到哈希表1中。如果此时正在插入一条数据B，如果有哈希表1有冲突，而哈希表2没有冲突，数据会被插入到哈希表2中。如果此时插入另一个keyC，经过哈希函数计算后发现，与两个哈希表冲突。这时候需要选择一个哈希表，先取出key，为C腾出位置，比如可以把C插入到A的位置，然后为A计算哈希值，如果A没有哈希表2冲突，直接将A插入哈希表2。cuckoohash在Github上也有一些对应的实现：https://github.com/efficient/libcuckooDynamicHashScheme上面提到的这些哈希表的实现可以认为是静态的，即在哈希表中可以存储多少数据是一开始就确定，不涉及扩张。但是在实际环境中，很多时候我们希望哈希表能够随着数据量的增长而扩展。下面介绍几种比较常用的哈希表实现，可以自动动态扩容。ChainedHash通过多个桶维护一个哈希表。如果存在哈希冲突，则将相同的键放在同一个桶中。如果桶超过指定容量，则用链表串联一个新的桶。每个桶一般都有一个指针来标识它的位置。一个key经过hash后，可以通过这个指针找到它所属的bucket。ExtendibleHash可扩展哈希（extendablehash）和链式哈希类似，都使用了桶的概念，也会有一个指针数组来执行桶。不同的是，可扩展哈希在计算出key的哈希值后，会将其值转化为二进制表示，然后会维护一个全局计数器，记录key需要取的二进制位数定位到桶指针数组；每个桶还有一个计数器，记录为本地计数器，表示定位桶需要多少二进制位。例如，在上面的例子中，第一个桶的计数器是1。当key位于这个桶中时，需要检索key的前一位。桶2和桶3的计数器都是2，需要取二进制的前两位。如果需要查询数据，首先要计算key的hash值，比如下图中的A。计算出它的hash值后，全局计数器为2，所以只需要取前两位，然后通过bucketpointer得到bucket的位置，遍历里面的数据就可以找到了。如果需要插入新数据，过程和查找过程类似，也是计算hash值，然后找到对应的bucket，将数据放入bucket的空闲位置。如果对应的bucket中没有空闲空间，此时需要进行split操作。先把globalcounter的值加1，然后创建一个新的bucket，把旧的对应的bucket的counter加1，让新的bucket的counter等于这个值。然后再通过这个key的二进制位把旧桶里的数据搬过来。比如下面的例子，需要插入keyC，但是它映射到的bucket已经满了。此时全局计数器增加到3，又增加了一个新的桶，计数器是旧值加一，也是3。然后根据新的基数重新存储旧桶，就会有此时桶中有空闲空间。更详细的可以参考：https://zhuanlan.zhihu.com/p/375039823LinearHash上面提到的可扩展哈希在分裂的时候需要扩展桶指针数组（也叫槽数组）。这时候一般需要在散列表上加一个全局锁，防止并发读写冲突。但是这种锁的粒度较大，容易造成哈希表读写的瓶颈。另一个线性散列维护一个分裂指针。当任何一个桶分裂时，分裂指针指向的桶也会分裂。这个方法介绍的不多，实际使用的应该也很少，就不详细介绍了。结论哈希表是一种高效的数据结构，大多数时候它可以在O(1)的情况下插入和查询数据。在数据库系统中，很多地方都会用到哈希表，比如上面提到的页表，页目录，以及执行sql查询时join的一些临时数据结构。但是哈希表的应用场景也是有限的，因为它存储的所有键都是乱序的，所以虽然适用于点校验，但不能用于范围扫描。在更一般的场景下，数据库中的表索引是使用最广泛的还是B+树。
