高级数据库九：不需要锁和闩的索引（二）

小灰灰 2022-06-03 08:49 114阅读 0赞

# 不需要锁和闩的索引（Latch-free OLTP Indexes Part II） #

## Bw-Tree Index ##

对于并发的跳表而言，我们不能在无锁的情况下有反向指针，因为CaS一次只能更新一个地址。

这个数据结构是微软在2010年左右做的，一开始微软想用的是Skip List，但是因为Skip List的限制，他们就设计了Bw-Tree。现在用Skip List的数据库，老师知道的只有MemSQL，它是由微软的数据库员工创建的。

Bw-Tree用到了下面的关键思想

### Mapping Table ###

有点类似哈希表，见下图

![15140633386730.jpg][]

在真正的树结构中，存储了特定的标识，如，101、102、104。以及记录了指向这些标识的“指针”，我们其实并不存储真正的指针，而是存储指向节点的标识，如，101的两个子节点指针分别存储了102和104。

在mapping table里，我们通过102和104得到了它的物理地址指针，再去访问。

通过这样的操作，可以允许对物理地址的页进行CAS操作。

### Deltas ###

这种操作的优点是，对于数据没有in-place的更新操作，同时还减少了缓存的无效时间。

我们每一个物理地址指针指向它所在的页，当我们有了一个修改操作之后，我们不直接更新Page 102的内容，而是打了一个标记，如，INSERT 50，并指向Page 102。

同时将Mapping Table的物理地址指针指到最新的标记位置。

![15140637247125.jpg][]

如果有两个线程同时更新同一个page，那么其中一个就会abort，那么它就可以再次尝试，直到成功（在这儿就非常类似Skip List的重复尝试，有人会好奇如果它永远没法成功的话，有没有办法解决。答案是，没有，因为这种情况发生的时候，意味着大量的读写正在进行，那么没有机制能够解决这个问题）。

![15140644115782.jpg][]

而查询操作就是从上往下进行搜索。假设我需要查询INSERT 50，现在从Addr找到了DELETE 48这个节点，因为和50无关则直接忽略，查到了INSERT 50，我们就知道50的信息，则可以直接停止。

如果我们搜索到了基础页，则可以做二分查找等我们正常的操作。

### 种类 ###

有两Deltas：

*  Record Update Deltas：插入、删除、更新页中的记录
 *  Structure Modification Deltas：Split/Merge 信息，具体的操作可以参考B+树，并看看PPT的内容。

### 合并更新 ###

我们不可能永远都将这些修改的信息留在那儿，形成一个长长的链表。

那么我们就需要将更新合并到基础页里面。

我们复制一份基础页，并逆序地将更新合并到新的基础页中，然后直接将102的Addr指针指向New 102，然后将Deltas更新和老的基础页标记为垃圾，进行垃圾回收。

![15140645483125.jpg][]

如果你合并失败，那么有两种情况，一种是在你合并的时候，又进行了一波更新；一种是别的线程在做合并。

这个时候，你就放弃合并，继续你的查询操作。

## ART Index(ADAPATIVE RADIX TREE) ##

Radix tree 是一个压缩trie。所以我们使用数字表示键，就在匹配的过程中逐个检查前缀，而不是比较整个键。

它有很多优点：

1.  树的高度仅与键的长度有关，且树结构唯一（B+ Tree与节点数有关，如果使用的是随机split，或者引入随机性，B+树的树结构是会改变的）
2.  键隐式存储，从根节点到叶子节点的路径表示键值。
3.  不需要再平衡。

它和Trie的区别如图

![15140746436410.jpg][]

Trie是将每1位都拆出，这样会导致树的长度过长。Radix的话，有几种方式进行压缩，一种是如上图在有区别的位时候进行区分，若前缀没有区别则进行压缩。

一种是将每2位（也可以是每4位，一般是2或者4位）拆除。如下图：

![Center][]

至于插入、删除、搜索这些操作，大家可以去搜一下资料。

### 二进制可比较键 ###

并非所有的属性类型都可以分解为基数树的二进制可比数字。

*  无符号整数：必须为小端(little endian)机翻转字节顺序。
 *  有符号整数：翻转二进制补码，使负数小于正数。
 *  浮点：归入组（neg与pos，归一化与非归一化），然后存储为无符号整数。
 *  复合：分别转换每个属性。

### 支持并行访问的ART ###

其实最早的ART是不支持无锁的并行访问的。

但是2016年有一个论文，讲述了如果实现。

[The ART of Practical Synchronization][]

在这儿就不细说了。

## 参考资料 ##

[课件][Link 1]  
[查找——图文翔解RadixTree（基数树）][RadixTree]  
[valgrind 的使用简介][valgrind]  
[Perf – Linux下的系统性能调优工具][Perf _ Linux]

[15140633386730.jpg]: https://lh3.googleusercontent.com/-ngnZzb81I2o/Wj78nIzu8xI/AAAAAAAAAWU/Ifu77rrxxC0a_UiAsCALa2bvxX4sCFCYACHMYCw/I/15140633386730.jpg
[15140637247125.jpg]: https://lh3.googleusercontent.com/-DbH0Zl605h0/Wj78nVouptI/AAAAAAAAAWY/TMLcgCcyGzUEEmimDQJEQj83T3Y1-YpSwCHMYCw/I/15140637247125.jpg
[15140644115782.jpg]: https://lh3.googleusercontent.com/-BsyLMUhX-Jw/Wj78njLLm9I/AAAAAAAAAWc/lFXIq2mcV5kpKdgvg69b-E3VaA23o0jlgCHMYCw/I/15140644115782.jpg
[15140645483125.jpg]: https://lh3.googleusercontent.com/-5xJ3jXOAjSE/Wj78oMmqlGI/AAAAAAAAAWg/syHI48Sm-hM1zwwgA8-YDhUpnlbdCta1wCHMYCw/I/15140645483125.jpg
[15140746436410.jpg]: https://lh3.googleusercontent.com/-aBKru1ApblE/Wj78oCakTwI/AAAAAAAAAWk/aENd_jZX78omtz_7oNV9CycpnBwG1NefwCHMYCw/I/15140746436410.jpg
[Center]: /images/20220603/b43195bc0ed640b79bcbcb019226b9cb.png
[The ART of Practical Synchronization]: http://15721.courses.cs.cmu.edu/spring2017/papers/08-oltpindexes2/leis-damon2016.pdf
[Link 1]: http://15721.courses.cs.cmu.edu/spring2017/slides/08-oltpindexes2.pdf
[RadixTree]: http://blog.csdn.net/yang_yulei/article/details/46371975
[valgrind]: http://blog.csdn.net/sduliulun/article/details/7732906
[Perf _ Linux]: https://www.ibm.com/developerworks/cn/linux/l-cn-perf1/index.html