在解决数据在存储设备上的存储格式以及数据在内存和存储设备间的传输交互后，现在要做的是如何使得代码能快速的找到其需要的数据。也就是在数据库的海量数据中，如何进行快速的检索。可以在原始数据的基础上建立一个辅助的检索的数据结构或者以特定的数据结构的形式组织数据的存储。主要的数据结构有两种：

1. hash table
2. tree indices

检索方式的设计主要有两个目标：

1. 在特定数据结构下，数据的存储组织
2. 并发安全控制

Hash Table

哈希表即将数据key通过哈希函数映射到一个特定array的offset上。Hash Table的设计包含两个部分：

1. hash function的选择
2. hash schema，用于解决hash冲突

哈希函数

常用的hash库有：

• CRC-64
• MurmurHash
• Google CityHash
• Facebook XXHash
• Google FarmHash

静态Hash Table

静态意味hash表的大小是固定的，不会动态的resize。其需要对所存储的数据量有一个大致的假设。常用的静态Hash schema有：

1. Linear Probe Hashing，当hash冲突时，就顺序向下探测空位置插入
2. Robin Hood Hashing，在linear probe的基础上，对每一个entry维护一个距离其原始hash值的offset。steal space的思想
3. Cuckoo Hashing，使用两个hash table，每个使用不同的hash函数，当有hash冲突时，依次移动，寻找空位。

解决非唯一键值的方法：

1. 分割的linked list，即hash表中的存储的value是一个linked list的起始，所有相同键值的存储早这个linked list中
2. 直接在hash table中存储重复的键值

动态Hash Table

区别于静态Hash Table，动态Hash Table机制中，不需要对存储的数据量有评估，动态Hash Table会根据存储的数据量大小，动态的扩容/缩容。三种经典的动态Hash Table模式：

1. Chained Hashing，hash的结果是bucket的编号，每个bucket是一个linked list。

2. Extendible Hashing，对chained hashing中的bucket进行reshuffling，多个slot可以指向同一个bucket

   
   
   图1. Extendible Hashing

3. Linear Hashing，维护一个指针指向下一个将要spilt的bucket。

   
   
   图2. Linear Hashing

Hash Table的优缺点

优点：一般情况下O(1)的时间复杂度，适合key search。
缺点：不能做range query

Tree Indices

数据库常用的树索引结构是B+ tree，是B-tree族中的一个，其余的还有：

• B-tree
• B*tree
• Blink tree(Paper: Efficient Locking for Concurrent Operations on B-Trees)

B+tree是一个M路的平衡树，是一种针对大block数据IO系统的优化方式，其搜索、序列访问、插入和删除的代价都是O(logn). B+tree中的每个节点除了root节点都是至少半满的（ [M/2-1, M-1] ）,每个内部节点有k个key以及k+1个非null的子节点。

B+tree的工程优化：

1. leaf node
   如图3，工程实现中可以将叶节点中的key和value分别存为一个数组，将key存为一个数组可以增强cache line效率，同时，value通常是page id的话，其大小是固定的，可以根据key的位置计算出value的offset。

   图3. leaf节点优化

数据库系统中，叶节点中leaf node的值是什么类型依据系统不同而不同。PostgresQL、IBM DB2、MSSQL Server和Oracle支持值为record id；SQLite、MySQL、MSSQL Server、Oracle支持值为tuple data。

2. 节点合并阈值
   一些数据库并不是直接在节点不半满时就执行节点合并，而是推迟合并或者使用后台线程周期性的检测并合并

3. 变长key
   四种方法可以解决：

   • 使用指针（太慢，不用）
   • 变长的node size（期望是page size一定，不用）
   • padding到固定长度（PostgresQL，浪费空间）

   • Key Map/Indirection，使用指向当前page内位置的指针

     
     
     图4. Key Map/Indirection

4. 重复key的解决方法

   • 直接存储重复的key
   • value list，key的结果指向list的起始（当数据过多超过page size时，可以使用overflow page解决）

5. Node内的key search

   • 线性搜索
   • binary search
   • Interpolation：根据已知的key分布，推断目标key的位置

其他优化：

1. prefix compression，在一个node中，key通常是相近的，可以将所有key的通用前缀存储起来

   
   
   图5. prefix compression

2. suffix truncation，如果多个键值根据前面的部分就能区别，则不必要存储完整的键值

   
   
   截断前
   
   
   截断后

3. Bulk Insert

4. Pointer Swizzling：对pin的常用page，可以直接在index中存储其在内存中的地址，而不是存储page id，每次都需要去buffer pool使用page map进行一次转化。

TRIE INDEX

B+tree的问题，所有的搜索结果必须在leaf nodes进行，至少可能会产生以此page miss？

使用一个bit来表示信息，比较时逐bit比较，也称为digital search tree或者前缀树

图6 trie index

Radix Tree

省略了一直只有一个子节点的trie index

图7 radix tree

写优化的树结构

1. Log Merged Structured tree：设计思想是减少写的负载和磁盘seek；适合在SSD上，减少page erase的，提升写效率；适合append模式的系统

2. Buffer Tree：将B+tree中的internal node改为带有缓冲的节点结构

   
   
   Buffer Tree

Table Index

table index是指table所有属性的一个子集的一个拷贝，将其排序而用于快速高效的属性检索。由数据库系统保证table和index属性值的一致性。一个表可能有多个索引，使用最优的索引是数据库系统的职责。索引的优点是加速查询，但是缺点是数据库系统有索引的存储代价和维护代价，亦即更新tale的代价会有所增加。

大部分数据库系统都会对一个table建立隐式索引，以此快速保证其主键完整性（非参照完整性）。

DBMS层面处理重复key

1. 将目标search key的值和其primary key绑定，这样就可以产生唯一的键。在搜索时使用partial key搜索的思想搜索目标值。

2. overflow leaf nodes，部分违背了B+tree的定义

   
   
   图8 overflow leaf nodes

索引概念

1. Clustered Indexs：table数据的实际page存储是按照某个search key的顺序进行存储的。这样可以避免在索引中找到的数据在多个page中，进而需要多个page IO。（MySQL默认即按照primary key做clustered index）

2. Dense Index / Sparse Index：密集索引是指所有的entry都在索引中出现，而稀疏索引则是部分entry在索引中出现。因为稀疏索引中只有部分entry，因此使用稀疏索引的前提条件是search key是聚簇索引。

   稀疏索引

3. Multilevel Index：当数据规模巨大时，索引的规模也巨大。可以在索引的基础上建立更高层的索引。因为索引必然是有序排列的，因此高层索引可以是稀疏索引。

4. Partial index：如果以<a,b,c>作为index key，基本所有的数据库系统都支持有前缀的partial key search，只有oracle、MS SQL Server支持任意key search。（named skip scan in Oracle）

5. Covering Indexs：如果一个queyr的所有涉及的属性都在索引中，则称其为覆盖索引。在此索引下，数据库系统加检索索引后不需要在去访问page获取tuple数据。

6. Index Include Columns：在Covering Indexs的基础上，将部分attribute的值添加到索引中，但是不作为索引的key。MySQL暂不支持。

7. FUNCTIONAL/EXPRESSION INDEXES：没有很多。PostgresQL支持。

8. INVERTED INDEX：存储从word到record的映射（适用于全文搜索/搜索引擎，例如Sphix，ElasticSearch），场景：

   • Phase Search：搜索含有给定word list的record
   • Proximity Search
   • Wildcard Search：正则匹配搜索

Bitmap索引结构

适合多个enum属性的与/或查询。是特定场景下，高纬查询的一种优化。

bitmap多维查询

空间数据检索

解决的问题：

1. 范围检索
2. 最近目标查询

数据结构有：

• k-d tree
• quadtree
• R-tree
• R*-tree

时间数据检索

• R-tree
• interval B+tree

多线程安全

多线程的数据安全、正确主要有两个部分：

1. 逻辑数据正确性：事务、线程视角的获取的数据应该是按照数据库隔离级别正确获取的数据。常使用锁概念来保证
2. 物理数据正确性：实际在操作内存、磁盘数据时的安全一致操作，常使用latch概念来保证

Lock用于隔离不同的事务，保护逻辑上的数据库数据。类型有共享锁、互斥锁、Update、意向锁。有专门的锁管理器，其会进行死锁检测和死锁恢复，常用的手段有waits-for、timeout、abort。

Latch用于隔离线程间对内存数据的访问。只有两种类型的latch：read latch于write latch。latch没有死锁检测和死锁恢复模块，依靠编程人员的规范性来避免死锁。

Latch的实现方式：

1. mutex
2. Test-and-Set Spin Latch，需要现代CPU支持
3. Read-Writer Latch, 需要良好实现的队列管理

Hash Table Latch

hash table操作都是一个方向的操作（hash->寻址->操作），因此是不会出现死锁的。
锁的粒度有：

1. page粒度的latch
2. slot粒度的latch

B+Tree Latch

B+树主要解决两个问题：

1. 并发的多线程访问
2. 保证一个线程来叶节点时，其余现在在merge/split时的安全性

加锁协议：latch crabbling/coupling

协议思想：当在树中进行遍历时，获取到当前节点的子节点的latch和父节点的latch，如果当前节点是安全的，则释放掉父节点的latch。安全的定义是：针对插入操作，节点不是满的；针对删除操作，节点是大于半满的。

优化策略，针对插入/删除/更新操作，先在B+tree中以对根节点read latch搜索，判断叶节点是否是安全的，如果是安全的，则直接对叶节点加write lacth，进行写操作。如果是不安全的，则释放所有的锁，再对根节点以write latch模式开始常规的latch操作。这样可以避免对根节点有过多的write latch加锁操作。这是一种乐观性latch的形式，乐观假设叶节点是安全的。

Blink-tree：针对B+tree并发的一种优化，核心思想是更新叶节点时，延迟父节点更新，做一个标记，当后面有新的写操作时，再进行相关的merge/split操作。

参考：
CMU 15-445/645 06
CMU 15-445/645 07
CMU 15-445/645 08
CMU 15-445/645 09
《Database System Concepts 7th editon》