内存引擎的索引结构以及整体的数据组织都是基于Masstree实现的。主体如图9-39所示。
图9-39 内存引擎主体结构
图9-15很好地呈现了内存引擎的组织架构。Primary Index（主键索引）在内存引擎的一个表中是必须存在的要素，因此要求表在组织时尽量存在primary index；如果不存在，内存引擎也会额外生成surrogate key（代理键）来用于生成Primary index。Primary Index指向各个代表各个行记录的Sentinel（行指针），由Sentinel来对行记录数据进行内存地址的记录以及引用。Secondary Index（二级索引）索引后指向一对键值，键值的value（值）部分为到对应数据Sentinel的指针。
Masstree作为Concurrent B+ tree（并行B+树），集成了大量B+树的优化策略，并在此基础上做了进一步的改良和优化。其大致实现如图9-40所示。
图9-40 Masstree实现方式
Masstree实现比于传统的B-tree，Masstree实际上是一个类似于诸多B+-树以trie（前缀树）的组织形式堆叠的Radix tree（基数树）模式，以Key（键）的前缀作为索引，每k个字节形成一层B+-树结构，在每层中处理Key（键）中这k个字节对应所需的insert/lookup/update/delete流程。图9-41为k=8时情况。
图9-41 k等于8时的Masstree
注：图来自于“Cache craftiness for fast multicore key-value storage” , Eddie Kohler et. al.
Masstree中的读操作使用了类OCC（Optimistic Concurrency Control，乐观并发控制）的实现，而所有的update（更新）锁仅为本地锁。在树的结构上，每层的interior node（内部节点）和leaf node（叶子节点）都会带有版本，因此可以借助version validation（版本检查）来避免fine-grained lock（细粒度锁）的使用。
Masstree除了lockless（无锁化）之外，最大的亮点是cache line（缓存块）的高效利用。Lockless本身一定程度避免了lookup/insert/update操作互相invalidate共享cache line（失效共享缓存块）的情况。而基于prefix（前缀）的分层，辅以合适的每层中B+-树fanout（扇出）的设置，可以最大程度的利用CPU prefetch（预取）的结果（尤其是在树的深度遍历过程中），减少了与DRAM交互带来的额外时延。
Prefetch（预取）在Masstree的设计中显得尤为关键，尤其是在Masstree从tree root（树根节点）向leaf node（叶子节点）遍历、也就是树的下降过程中。此过程中的执行时延大部分由于内存交互的时延组成，因此prefetch（预取）可以有效地提高masstree traverse（遍历）操作的执行效率以及cache line（缓存块）的使用效率（命中）。
