ART Index
(26/2/2021)
0. 内存索引实现方式
- 比较树（comparion），比较key值，排序后树型存储；
- 哈希表（hash），散列后存储到数组中；
- 字典树（trie），将key值拆分成token，按照前后顺序组成树
我们使用基于字典树形式实现的ART算法索引内存中的所有数据.
1. ART简介
ART（The Adaptive Radix Tree）可变的基数树，在Radix tree 的基础上，优化增加可变特性，其核心是优化空间的利用率。每个节点的空间大小不再相同，而是根据需要使用不同的节点类型。
ART设计了4种Node内部节点打类型：Node4，Node16，Node48和Node256，这里数字的含义是包含了多少个元素。比如Node4只能存放4个元素，Node16存放16个元素，Node48存放48个元素，Node256存放256个元素。
- Node4有两个数组，一个数组是vector key(4)，一个是vector<Tree*> pointer(4)：key里是4个元素，每个元素是一个Byte；pointer存了对应的子树指针（指针是8个字节）。例如我们要存储字符串art（如上图所示），树的第一层的node是Node4类型，第一个数组key存了字母a，相应地，第二个数组pointer的第一个元素存了a对应的子树的指针。
- Node16也是两个数组，结构与Node4一样，只不过可以存16个元素。
- Node48有两个数组，只不过第一个数是256个元素（这样就涵盖了Byte所有表示的全部可能性），第二个数组是48个元素（每个元素还是指针），这也是为什么叫Node48的原因。所以可以看到，虽然第一个数组可以存256个元素，但实际上只存了48个元素，有一定的空间浪费，但为了效率，只能这么做了。
- Node256只包含了一个数组vector<Tree*> pointer(256)，因此可以直接通过下标访问，
判断对应的指针是否存在。
上面四中类型就是ART最重要的数据结构。每次新生成节点的时候，都是Node4类型，也就是最小的。插入数据的时候，如果发现放不下了，就要扩充节点容量变成比当前大一级的节点
2. 并发控制机制-ROWEX
ROWEXREAD_OPTIMIZED WRITE EXLUSION，读优化写互斥同步机制。
- 保证读操作不阻塞，总是成功。读不进行加锁操作
- 在修改节点前加锁，该锁仅对写产生互斥。
- 为了保证读操作的一致性，就要求写操作是原子性操作。ART 每个元素的空间位置固定，不像B+树的rebalance后，空间位置发生变化。因此，可以进行原子化操作。
