MOT索引

在比较了各种最先进的解决方案之后，我们选择了Masstree作为索引，因为它显示了点查询、迭代和修改的最佳总体性能。Masstree是Trie和B+树的组合，用以谨慎利用缓存、预取、乐观导航和细粒度锁定。它针对高争用进行了优化，并对其前代产品增加了许多优化，如OLFIT。然而，Masstree索引的缺点是它的内存消耗更高。虽然行数据占用相同的内存大小，但每个索引（主索引或辅助索引）的每行内存平均高了16字节——基于磁盘的表使用基于锁的B树，大小为29字节，而MOT的Masstree大小为45字节。

我们的实证研究表明，成熟的免锁Masstree实现与我们对Silo的强大改进相结合，恰能为我们解决这一方面的问题。

另一个挑战是对具有多个索引的表使用乐观插入。

• Masstree全球GC：快速按需内存回收
• ARM架构支持

我们为Masstree开放源码实现贡献了我们的Masstree索引改进，可以找到。

MOT的主要创新是增强了原有的Masstree数据结构和算法，它不支持非唯一索引（作为二级索引）。设计细节请参见非唯一索引。

MOT支持主索引、辅助索引和无键索引（受不支持的索引DDL和索引中提到的限制）。

图 1 非唯一索引

上图描述了一个MOT的T表的结构，它有三个行和两个索引。矩形表示数据行，索引指向指向行的哨兵（椭圆形）。哨兵用键插入唯一索引，用键+后缀插入非唯一索引。哨兵可以方便维护操作，无需接触索引数据结构就可替换行。此外，在哨兵中嵌入了各种标志和参考计数，以便于乐观插入。

查找非唯一辅助索引时，会使用所需的键（如姓氏）。全串联键只用于插入和删除操作。插入和删除操作总是将行作为参数获取，从而可以创建整个键，并在执行删除或插入索引的特定行时使用它。