Mongodb 默认存储引擎 WiredTiger 的数据结构探究
我们知道 Mongodb 默认使用的存储引擎是 WiredTiger。了解存储引擎的数据结构是十分重要的尤其是对于服务端的同学，只有你了解了它才能更好的使用 Mongodb。关于 Mongodb 我们在这里不做介绍，我们主要四回答以下两个问题才搞清楚 WiredTiger 的数据存储结构。
问题一 B-tree 还是 LSM tree ?
LSM tree
MongoDB 中的 LSM (Log-Structured Merge-tree) 是 WiredTiger 存储引擎提供的一种索引数据结构选项。它主要有这些特性：
- 内存写入缓冲:
新的写入操作首先被添加到内存中的一个称为memtable的数据结构中。 memtable通常使用平衡树(如红黑树或AVL树)实现,以保持键的有序性。 2， 顺序写入磁盘:
当 memtable 达到一定大小阈值时,其内容会被刷新到磁盘上,形成一个不可变的 SSTable (Sorted String Table)文件。 这个过程是异步进行的,不会阻塞新的写入请求。 - 多层结构:
LSM树通常维护多层SSTable文件。 较新的数据在较高层(如Level 0),较旧的数据在较低层。 每一层的大小通常比上一层大几倍。 - 读取操作: s 读取时,首先检查 memtable。 如果 memtable 中没有找到,则按从新到旧的顺序检查SSTable文件。 可能使用布隆过滤器来快速确定一个key是否可能存在于某个SSTable中。
- 合并和压缩:
后台进行定期的合并和压缩操作,将多个小的SSTable合并成更大的SSTable。 这个过程会删除过时的数据,保留最新的值。 - 写放大:
LSM树的设计会导致写放大,即实际写入磁盘的数据量大于用户请求写入的数据量。 这是因为同一条数据可能被多次写入不同的SSTable。 - 空间放大:
由于存在多个版本的数据和未压缩的文件,LSM树可能会导致一定程度的空间放大。 - 读放大:
读取操作可能需要检查多个 SSTable,导致读放大。 这可以通过布隆过滤器和缓存等技术来缓解。 - 配置选项:
MongoDB允许用户通过命令行参数来选择使用LSM索引,并配置相关参数。 - 性能特点:
LSM树在写入密集的场景下表现优异,特别是对于随机插入操作。 读取性能,尤其是点查询,可能不如B树索引。
B-tree
B-tree 是 Mongodb 中默认使用的数据结构。特性包括这些:
- 树形结构:
B-tree是一种自平衡的树形数据结构。 它由根节点、内部节点和叶子节点组成。 每个节点可以包含多个键值对和指向子节点的指针。 - 节点组成:
每个节点(称为bucket)有固定大小,通常为8192字节。 节点包含keynode和keydata两部分。 keynode存储固定大小的结构,包含指向子节点的指针和文档位置。 keydata存储可变长度的BSON格式键值。 - 数据排序:
键值对在节点内按键的顺序排列。 这种排序允许快速的查找、范围查询和排序操作。 - 查询过程:
从根节点开始,根据键值比较逐层向下遍历。 通常只需3-4次I/O操作就能定位到目标文档。 - 插入和分裂:
当节点满时,会发生分裂操作。 分裂会创建新节点,并将一半数据移到新节点中。 这个过程可能会一直传播到根节点,保持树的平衡。 - 性能特点:
提供稳定的查询性能,最坏情况下复杂度为O(log n)。 适合大规模数据集和磁盘存储系统。 - 灵活性:
支持精确匹配、范围查询和排序操作。 可以创建复合索引,包含多个字段。 - 优化技术:
使用前缀压缩等技术来减少索引大小和提高效率。
为什么 MongoDB 默认使用 B-tree 作为其数据存储机制？
B-tree 能够在读取和写入操作之间提供良好的平衡。 B-tree 结构支持高效的数据检索和范围查询，因为数据是有序存储的，这使得对连续键值范围的查询变得快速和直接。此外， B-tree的设计允许在不影响整体性能的情况下进行高效的插入和更新操作，这对于维护数据的一致性和完整性至关重要。
B-tree 的这些特性使其成为在需要频繁读写操作的场景中的一个理想选择。MongoDB 作为一个通用的 NoSQL 数据库，需要能够处理各种各样的工作负载，包括但不限于实时分析、内容管理和移动应用程序后端。在这些应用中，平衡读写性能对于确保系统响应性和用户体验至关重要。
此外， B-tree的结构允许 MongoDB 实现强大的事务支持，这对于需要高度数据一致性和原子性操作的应用来说是非常重要的。通过使用 B-tree，MongoDB 能够确保事务的原子性、一致性、隔离性和持久性（ACID 属性）。 总的来说，MongoDB 选择 B-tree作为默认存储机制，是为了在广泛的应用场景中提供平衡的读写性能、高效的查询能力和强大的事务支持。
问题二 B-tree 还是 B+ tree
有不少文档有的说 Mongodb 使用的是 B-tree, 有的说是 B+ tree。 这个问题让我也很郁闷，在这里我们追根溯源一下。这篇帖子相信能回答。
在网页内容中，用户 Ars Roseregen 表达了对 WiredTiger 索引数据结构的疑惑。他认为 WiredTiger 使用的是 B-Tree，直到他查阅了一些文档，这些文档称 WiredTiger 使用的是 B-Tree（具体指的是 B+Tree）。然而，当他检查 WiredTiger 的源代码时，没有找到叶节点之间的指针，这是 B+Tree 的一个典型特征。这个发现让他感到困惑，因为另一份文档又提到 WiredTiger 使用的是 B-Tree。
WiredTiger 团队成员 Keith Smith 回应了这个问题，解释说他们称为 “B-Trees”，但这种称呼可能并不精确。他指出，WiredTiger 的设计包含了一些不符合传统 B-Tree 或 B+Tree 定义的优化。WiredTiger 的 B-Trees 存储了所有的键和值在叶子页面中，这一点与 B+Trees 相似。但是，WiredTiger 没有提供从一个叶子页面直接到另一个叶子页面的链接，因为它总是将更新后的页面写入到文件的新位置。WiredTiger 通过父页面来移动到下一个叶子页面，这种方法因为缓存机制而高效。最后，Keith Smith 引用了 Douglas Comer 的论文，指出即使在 B+Trees 中，叶子节点的链接也不是一个严格的要求。
怎么理解 WiredTiger moves from one leaf page to the next by going back through the parent page.
WiredTiger 如何通过父页面移动到下一个叶子页面
在 WiredTiger 的索引结构中，当需要从一个叶子页面移动到另一个叶子页面时，它并不直接链接到下一个叶子页面。相反，它采用了一种通过父页面来实现这种移动的机制。这意味着：
树状结构的特点：WiredTiger 的索引结构类似于树形结构，其中每个节点都有一个或多个子节点。叶子页面位于树的底部，包含了实际的数据。
无直接链接：与 B+Tree 不同，WiredTiger 的叶子页面之间并没有直接的链接指针，通常 B+Tree 的叶子页面会有一个指向下一个叶子页面的指针，以便顺序遍历。
通过父页面导航：当需要访问当前叶子页面之后的叶子页面时，WiredTiger 会首先返回到它们共同的父页面。父页面包含了指向其子叶子页面的指针。
高效的缓存策略：WiredTiger 的设计利用了缓存策略，通常在访问叶子页面时，相关的父页面也会被缓存。这样，当需要通过父页面移动到下一个叶子页面时，可以直接从缓存中获取父页面的信息，从而提高效率。
文件写入优化：WiredTiger 在更新页面时，通常会将更新后的页面写入到文件的新位置。这种做法避免了在原有位置进行更新，从而减少了碎片化，并且允许在不同的文件版本之间进行快速切换。
灵活性和性能：通过这种设计，WiredTiger 能够在保持高性能的同时，提供更大的灵活性。它可以更好地管理磁盘空间，并且在处理大量数据时，能够更有效地进行页面的读写操作。
总结来说，WiredTiger 通过父页面来移动到下一个叶子页面的设计，是一种优化的策略，它利用了缓存机制，以提高数据访问的效率和性能。这种设计虽然与传统的 B-Tree 或 B+Tree 有所不同，但它为数据库的索引结构提供了更多的灵活性和优化空间。