主要介绍T树，跳表，Bw树，Judy Array，ART和Masstree。涉及到索引的物理结构，如何在索引上实现查找、插入和删除，以及插入删除引起的节点的分裂与合并，以及多线程在索引上怎么实现Latch-Free的并发的。

基础知识

原始的B+树是为面向磁盘的DBMS设计的，在内存数据库上对索引进行重新的设计（但是内存数据库索引进行的改进和设计又是基于内存数据库的什么特性进行的呢？）。

平衡二叉树

前缀树
Trie Tree又叫字典树，单词查找树。关键字保存在一条路径上。

基数树
Radix tree是前缀树的改进，尤其适用于稀疏的长整型数据的存储，与前缀的区别在于，一条路径上代表的可以不是单个字符，可以以1个或多个字符叠加作为分支，避免了长key导致树的深度太大。

基数树和前缀树

T-tree

基于平衡二叉树，在节点中不存key，而是存指向数据的指针

T-Tree的结构
如图所示，每个节点中除了指向数据的指针，会记录节点的边界key的最大最小值，小于最小key的节点指针，大于最大key值的节点指针，以及指向父节点的指针。
内部节点对空间利用率有要求，不小于某个值，否则进行分裂或合并。（对叶子节点可能没有要求）
操作

1. 查找：看search key是否在min-k和max-k之间，如果在，按照指针去data table中一个一个比较查找（或节点内按序排列，二分查找）。
2. 插入：先用查找找到要插入的位置，记下查找过程中遇到的最后一个节点。判断是否有足够的空间，有的话直接插入；没有空间时会直接插入，然后选择把最小的插入到左孩子或者最大的插入到右孩子中（递归操作，就是如果它的孩子也满了，继续往下插——想想AVL中的插入，插入的总是一个叶子节点吧），直到叶子节点，如果叶子节点已满那么对它进行分裂，产生它的左孩子或者右孩子，然后再进行旋转平衡。
3. 删除：这就和插入比较像了，先找到所在节点，删除后发现如果不到m/2，那么找它的左孩子的最大键值或右孩子的最小键值进行补充——叶子节点被上面的给抽光了，删除这个节点，旋转平衡

优点是用的空间更少了，因为根本就没存键（单存了一个指针，与search key的对比都是通过指针找到这个数据进行比对key的）；和B树一样，叶子节点和内部节点相同，都是包含键值对的
缺点是平衡操作复杂，难以实现安全的并发；在节点内进行范围查询或者二分查询需要根据指针找到数据比对，效率低

跳表

实现动态的有序索引最简单的方法。是一种随机化的数据结构。跳表就是多层的链表，用额外的指针来跳过中间节点。

跳表结构.png
一个跳表由几个层level组成；第一层（最底层）就是一个简单的有序链表，包含所有的key；上面一层的节点数是它下一层的一半；除了最底层的其他层的节点还会有一个down指针指向下一层同key节点。
操作

1. 查找：总是从top开始找起，逐渐向下
2. 插入：因为上层的节点数总是下层的一半，插入时除了l1必须插入外，在l2掷硬币，正面l2插入，再看l3也是正面插入……直到掷到反面。
3. 删除：首先通过设置一个flag告诉其他线程它已经被删除了（逻辑上删除），没有线程使用它后物理删除。

并发控制
插入与删除都不需要使用闩，只用CaS就可以了（只支持单向链表，CaS无法更新双向链表的两个指针）

但是因为CaS一次只能更新一个地址，所以不能有反向指针。（所以怎么实现原子性的更新多个地址呢）

Bw-Tree

（结合Building a Bw-Tree Takes More Than Just Buzz Words）
要点

1. Mapping Table：映射表是讲page id与地址进行映射，而在B树上完全节点之间“完全抛弃”了物理指针，用的都是pid（逻辑指针），然后根据这个pid再去找其地址。更新映射表通过CaS实现。
2. base node and delta chain：也分为中间节点和叶子节点，中间节点存的是(key, NodeId)，叶子节点存(key, value)，都是按key有序存放，可用二分法在节点内查找。更新不直接更新在节点中，而是添加一个delta recode到delta chain（注意在每次更新完成后，也就是添加delta Record后，映射表中的地址会变更为指向这个最新的delta Record），delta chain和base node是通过物理指针相连。
3. Consolidation and GC：delta chain是有长度限制的，每当到达最大长度，要把这些更新给写入到节点中去。在Consolidation时，会创建一个新的节点，把delta record写入，然后更新映射表。那么原来的base node也就需要回收了。Bw-Tree的垃圾手机是基于epoch的，下面详解。
4. 结构修改：用特殊的delta record表示先表示修改操作，然后才是物理上的修改。
   此外还有对与Non-unique key的支持，对于范围查询的处理（把节点内容拷贝以便进行并发和快速随机访问，一个节点读完后根据low_key或high_key去找上一个或下一个节点）和映射表扩展一些问题（虚拟地址空间）。
   Bw-Tree的结构.png
   Bw-Tree节点结构.png
   操作
5. 查找：和B+树一样，但是如果遇到的delta chain，找到含有要找的key的rocord就可以停止了，否则在base node中进行二分查找。
6. 插入：就直接写到delta chain中，通过CaS更新映射表，如果满了就Consolidation。
   3 删除：和插入一样

在Bw树上做的优化

1. Delta record的空间预分配：不预分配时delta record是分配在堆中的，可能会发生未命中，所以预先在节点中分配一些delta chain的空间
2. GC：原始的Bw-Tree的GC是基于epoch的，实现原理如下：索引维持着一个全局的epoch对象的列表，并且每隔固定时间如10ms添加一个。每个线程（操作）在 开始的时候未访问索引前都要先在epoch登记，线程完成操作后从登记的那个epoch移除。每个被线程删除的对象会先被添加deletion标记，然后加入到删除它线程所在的epoch中。当一个epoch中没有活跃线程了，就可以把添加到它里面的标记为deletion的对象由回收线程回收。——图a显示的是线程t2在epoch103中添加了一个要回收的节点，索引又加入了一个新的epoch104，此时epoch101中已经没有活跃线程了，可以全部回收。
   上面的GC扩展性差，每个线程都需要等级，需要counter来记数活跃线程，易产生cache coherence traffic（缓存一致性冲突）。
   改进：不再以epoch为中心了，而是以线程为中心（本地化）。索引维护一个全局epoch， 流程如下：1 线程开始，其线程epoch=当前全局epoch；2 线程加入一个垃圾节点，加指针，垃圾节点的epoch=当前全局epoch； 3 线程结束，先把线程epoch修改为当前epoch，然后调用GC。这个线程会先找最小的线程epoch，然后把它里面垃圾节点的epoch小于最小线程epoch的给回收掉。图b中线程1调用GC，知道最小线程epoch为100，那么线程1里面节点epoch为98,99的节点就可以回收了。

GC.png

3. Fast Consolidation：如何把delta record中的数据写入到base node中
   Consolidation会创建一个新的节点，然后更新映射表，原来的节点+delta record就成了垃圾。但是新的节点中的key会面临重新排序问题。这里的改进是通过delta record的offset来实现的，delta record的offset会标记好要插入或者删除的位置以避免重新排序。

节点的分裂与合并

节点的分裂与合并.png
如图所示，节点N0分裂时，首先创建一个新的节点N1，转移N0中的数据，设置N1的属性，把N1加入到映射表中去，然后在N0加入一条特殊的dleta record △split告诉其他线程该节点尚未分裂结束，正处于分裂的中间状态，修改N0的属性，并且△split有一个指向N1的逻辑指针（在里面存了个N1），在查找的时候，search key大于等于N0的high_key，会去它的右兄弟节点N1中找（来自Blink-Tree）
节点合并时，如N1要合并入N0时，首先在N1上用特殊的delta recodt △remove标记表示该点将要移除，也阻止其他线程访问N1的delta chain，让所有访问N1的线程转而去访问N0（为了找到N0，会存一个指向父节点的物理指针）。之后在N0上添加一个delta record △merge，表示有节点要并入它，这个record会存一个N1的物理指针，这样N0和N1就算是一个逻辑节点了（△merge中有一个merge key也就是N1的low_key帮助search key比较是访问N0还是N1）。最后在N0和N1的父节点P上加一个△delete,其中记录着在合并前的分隔项和合并后的分隔项，在之间的直接通过逻辑指针指向合并后的节点（不是很清楚又何必要）。

索引在实现上的问题

索引在实现上除了大的结构性上的考虑，还要考虑细节上的GC，内存池，非唯一键，变长键以及压缩问题。
GC：有一些通用的方法供选择，reference counter(对于多核CPU，增减counters易产生缓存一致性冲突问题)，Epoch-based Reclamation(前面的原始Bw-Tree像是epoch-based + reference counter来实现group gc)，Hazard Pointers（尚未了结）等等。
Memory pools: 更应该称内存分配问题，对于新的节点如何分配，删除的节点如何回收。应该尽量避免直接调用malloc和free。如果所有的节点都是同样大小（事实上绝大多数也是如此），可以维持一个可用节点的pool，当需要插入时从pool中取一个空闲的，否则可以再创建一个新的节点；删除时还给free pool。需要一些策略来控制pool的大小（收缩）
非唯一key：duplicate keys当成普通的存，看起来就是多个相同的key值对应多个不同的value；Value Lists 一个key，后面挂一个对应的多个值的list。
变长key：1.pointers 直接就存指针了，指向元组的属性 2 变长节点 内存管理 3padding 总是按最长的key来分配空间 4. key map/indirection 和pointer有点像，B+树叶子节点中，存一个有序的指针数组，指向key+value list（也在节点内）。
压缩：前缀压缩和后缀截断。在同一个叶子节点内有序的key很可能有相同的前缀，相同的前缀只存一次。在中间节点中，key只用来导向，所以能区分出来就行了，比如abcsmd和ueisjla之间前三个字母就足以区分，后面的就不存了。

中间节点的key不能知道在不在索引中，总是需要到叶子节点中遍历才能知道。所以就有了下面的索引

Trie Index

前缀树
n-bit span trie也就是2^n-1路trie

Radix Tree

在前缀树的基础上，忽略所有只有一个孩子的节点

Trie Tree.png
Radix Tree.png
Radix Tree.png

前缀树有一些变体，如Judy Arrays，ART index和Masstree

Judy Arrays

256路基数树的变体，支持节点的自适应表示
节点在header中不存自己的元数据，会把元数据成128位的Judy Pointers存在父节点上，包含节点的类型，存的数据量，子关键字的前缀（或者如果只有孩子，存的是这个孩子的最后的Value，因为是基数树），64bit的孩子指针
有三种数组类型：

• Judy1:Bit array映射integer keys到真假
• Judy2: Map integer keys to integer values
• Judy3: Map 变长key到integer values

三种节点类型，根据数据的稠密程度选择。每个节点可以存最多256个数字
+Linear Node:稀疏
+Bitmap Node：一般的
+Uncompressed Node：稠密的
十分钟了解Judy Arrays

ART Index

自适应基数树，应用于Hyper中。
在基数树中每个节点可以存储任意长度的键切片，但是在数据库中索引在很多情况下会被频繁修改，每个节点固定长度的键切片会造成时间和空间的浪费，于是Hyper实现的自适应基数树ART的节点会根据长度的不同分成若干种，根据数据的变化自行调整。

ART的结构.png
ART内部节点类型.png

节点类型有Note4, Note 16, Note 48和Note256。Note4表示的是只存8bit的数字，前面存key的数组和后面存数据（指针？）的数组是对应的。

主要特点是：
树的高度取决于键的长度；更新与删除不涉及树结构的调整，不需要平衡操作；到达叶子节点的路径就是键；时间复杂度取决于键的长度，与数据量无关，如果数据的增加远远超过键长度的增加，那么使用ART性能收益很大。

在并发控制上，两种机制

1. 乐观的闩连接：写不阻塞读；每个节点都有一个版本信息(counter)；写获得对应的闩后更新版本信息(counter++)；读操作会在读下一个节点前验证版本信息是否发生了变化。

   
   乐观的闩连接.png

2. 乐观读写排斥：所有节点都有一个互斥锁，阻塞其他写而不阻塞读；读不需要获得锁或闩，也不用检查版本信息；写需要保证同一个节点读操作的数据一致性，也就是写操作需要用原子指令完成。
   （看完The ART of Practical Synchronization后再来补充）

MassTree

B+树和Radix Tree的混合体，把键分成多个部分，每个部分为一个节点，每个节点内部是一个B+树；
把长键划分成了多个固长部分，每个固长部分可以通过int表示；
每个节点是一个B+树
并发控制时用的是read-copy-update(RCU)，写不会阻塞读，更新数据时先更新在副本上，然后一次性替换旧数据，因此读不会造成CPU缓存无效。