存储引擎层是键值数据的核心单元。数据存储在存储引擎中，并采用索引结构提升存储引擎中数据的存取性能。存储引擎对上层提供Put、Get、Del和Range函数接口，这些接口分别负责往该存储引擎内部插入/修改键值对、查询键值对，删除键值对和范围查询键值对。
一般来说，存储引擎主要分为4个模块：索引模块、存储模块、持久化模块和空间分配/垃圾回收模块。其中，存储模块负责键值对的物理存储，索引模块负责对每个键值对的快速定位，持久化模块负责对存储模块的持久化和可恢复性的保证，空间分配/垃圾回收模块负责空间的申请、分配及当空间使用率过高时的垃圾回收任务。对于部分有特殊需求的键值数据库，可能还会有额外的模块，如加解密模块和压缩模块等。
根据采用的索引和存储结构的不同，典型的存储引擎可以分为三大类。
1）基于哈希表的存储引擎。
2）基于B+树的存储引擎。
3）基于LSM-tree的存储引擎。
基于B+树的存储引擎
B+树是一种平衡的、多叉的树形结构，能够支持 O （log n ）的插入和查询时间复杂度。B+树的整个结构是有序存储的，这使得B+树能够高效地支持范围查询；在空间放大维度，B+树能够达到70%的空间利用率。综上所述，B+树有较好的综合性能，在现代的诸多存储系统中，B+树索引很常见，例如关系数据库MySQL的默认存储引擎InnoDB。在键值数据库中，采用B+树作为索引结构的系统有BerkerlyDB、微软的Hekaton等。
B+树结构是一棵多叉的平衡树，每个内部节点存储了 k 个键和 k +1个指针（ ，其中 m 为最大容量），每相邻两个键划分出一块键范围。内部节点中的键可以将键的取值范围划分为 k +1个子区域，每个子区域对应的指针指向的是一棵子树，子树中的所有键均属于子区域。每个叶子节点可以存储最多 m 个键值对。当一个叶子节点满时，叶子节点分裂为两个新的叶子节点，并且将新节点及两个节点的分割键作为一个新的索引项插入到父亲节点中去。
常见的B+树结构如图4-5所示。图所示是一棵层高为2的B+树，内部节点由两个整数键5和9，以及3个指针构成。最左边的指针指向的子树是一个叶子节点，在节点中包含两个键值对，其对应的键均小于5。当连续往B+树中插入2和3之后，最左边的叶节点超过最大能存储的容量，叶节点发生分裂操作，分裂后的B+树结构如图4-6所示。
数据库服务器通常在许多线程中运行，以服务于许多用户，并利用多个处理器核心和许多使用异步I/O的磁盘。即使是单线程的应用，例如在个人计算机上，数据库维护和索引调整的异步活动也需要并发线程，因此需要对B+树索引进行并发控制。由于B+树的树形结构会不断动态调整，要实现一个正确的多线程B+树，存在着较大的设计挑战。目前来说，实现B+树的并发，可以采用以下3种机制：①锁耦合；②乐观锁机制；③无锁机制。
1.锁耦合机制
锁耦合机制是B+树中应用最为广泛的一种加锁方式。为了保证多线程安全，如果给整棵B+树加锁（见图4-7a），无疑会对整体的吞吐产生较大的负面影响，因为每次写请求都会阻塞整棵树上的所有后续读/写线程。另一种方式是在结点级别加锁，每次执行读/写访问时，锁住从根节点到叶节点路径上的所有结点（见图4-7b），这样每个读/写线程都会锁住一条路径上的所有节点。锁耦合机制就是一种节点级别的加锁方式，但是路径上的节点的锁会更早地释放，如图4-7c所示，同时能保证线程安全。在锁耦合机制中，每个线程同时最多拥有两个节点的锁，分别为父节点和孩子节点。父节点的节点可以在孩子节点的锁获取之后释放，这样可以充分减少每个节点加锁和释放的临界区大小，从而最大化多线程性能。
图4-7 B+树的加锁方式
2.乐观锁机制
采用锁耦合机制，每个读/写线程仍然是互相阻塞的，而乐观锁机制试图减少写线程对读线程的阻塞，并进一步减少加锁的数量。为了实现无阻塞读线程，B+树结构需要做相应的适配。在B+树的中间节点中增加字段，存储中间节点的兄弟指针，以及节点和兄弟节点的分割键。内部节点除节点内部的锁字段之外，还额外维护一个写版本号。每当写线程对节点完成修改之后，先对写版本号完成自增操作，随后释放写锁。每当读线程访问一个节点的时候，首先记录节点版本号，在完成对节点的访问之后检测节点版本号是否发生变化，如果节点写版本号发生变化，读线程重做对该节点的访问，否则意味着节点访问过程中该节点并未发生写操作，因此读节点操作成功执行。
3.无锁机制
Bw-tree是著名的无锁B+树结构，并且是微软的Hekaton的核心索引结构。Bw-tree通过无锁的方式来操作B+树，提升随机读和范围查询的性能。它的核心的思想是把B+树的页（page）通过page id（PID）映射到map，map的[key，value]变成[PID，page value]，把直接对page的修改，变成一个修改的操作记录，加入到“page value”。所以“page value”可能是一个“base page”，即page原始的内容，和一串对page修改形成的记录的链表，而在修改记录链表中加入一个修改记录节点可以很容易变成一个无锁的方式来实现。另外，对B+树的split和merge操作也通过类似的原理，把具体的操作细化成好几个原子操作，避免传统的加锁方式。
总之，乐观锁机制是对锁耦合机制的一种优化，前者大大减少了加锁数量和临界区长度，从而大大提升了并发性能。在乐观锁机制中，读线程是不会被阻塞的，但是写线程会互相阻塞，从而在写密集的负载下，乐观锁机制仍然存在较大的性能瓶颈。无锁的设计能够使得读写线程互不阻塞，从而有望实现更高的多核可扩展性。
