Why'sTheDesign（Why'sTHEDesign）是一系列关于计算机领域编程决策的文章。在本系列的每篇文章中，我们都会提出一个特定的问题，并从不同的角度讨论设计。优缺点，影响具体实施。概述MongoDB是一个通用的、面向文档的分布式数据库[^1]，这是MongoDB的官方介绍。与传统的关系型数据库MySQL、Oracle、SQLServer不同，MongoDB最大的特点是“面向文档”。由于数据存储方式不同，对外提供的接口不再是大家熟知的SQL，所以分为NoSQL，NoSQL是相对于SQL的，很多我们熟悉的存储系统都是分为NoSQL的，比如：Redis、DynamoDB[^2]和Elasticsearch。sql-and-nosqNoSQL常被理解为无SQL（Non-SQL）或非关系型（Non-Relational）[^3]，但也有人理解为不仅仅是SQL（NotOnlySQL）[^4]，它深究这个词的含义和出处，可能意义不大。第二种解释通常用于营销。我们只需要知道，MongoDB存储数据的方式与传统的关系型数据库完全不同。MongoDB的架构与MySQL非常相似。两者都在底层使用了可插拔的存储引擎来满足用户的不同需求。用户可以根据数据特点选择不同的存储引擎。最新版本的MongoDB使用WiredTiger作为默认存储引擎[^5]。mongodb-architecture是MongoDB的默认存储引擎。WiredTiger使用B-tree作为索引的底层数据结构，但是除了B-tree之外，它还支持LSMtree作为可选的底层存储结构。LSM树的全称是Log-structuredmerge-tree，你可以在MongoDB中创建一个基于LSM树的集合（Collection）[^6]，命令如下：db.createCollection("posts",{storageEngine:{wiredTiger:{configString:"type=lsm"}}})在这篇文章中，我们不仅会介绍为什么MongoDB默认的存储引擎WiredTiger选择使用B-tree而不是B+-trees，还会比较两者的性能和应用场景B树和LSM树帮助读者更全面地理解当今的问题。由于设计需要比较两种不同的数据结构和B-tree的区别，这里分两小节介绍为什么B+树和LSM树没有成为WiredTiger的默认数据结构：MongoDB作为非关系型数据库，非常对数据的需求没有关系型数据库那么强烈。追求读写单条记录的性能；大多数OLTP数据库都面临着读多写少的场景，而B树和LSM树在这种场景下有更大的优势。优点;以上两种场景是MongoDB需要面对和解决的，所以我们将在这两种常见场景下比较不同的数据结构。Non-relational上面我们已经多次提到，MongoDB是一个非关系型文档数据库。它完全抛弃了关系数据库的体系后，在设计和实现上都非常自由，不再需要遵循SQL和关系数据库。大型数据库的系统允许更自由地优化特定场景，在MongoDB假设的场景中遍历数据并不是一个普遍的需求。mysql-innodb-b-plus-treeMySQL使用B+树，因为只有B+树的叶子节点才能存储数据。通过指针连接树中的各个叶子节点可以实现顺序遍历，而遍历的数据在关系型数据库中是很常见的，所以选择[^7]完全没问题。MongoDB和MySQL在多种不同数据结构之间进行选择的最终目的是减少查询所需的随机IO次数。MySQL认为遍历数据的查询很常见，所以选择了B+树作为底层数据结构，而放弃了。节点存储数据，但MongoDB面临一个不同的问题：虽然针对遍历数据的mongodb-wiredtiger-b-tree查询比较常见，但MongoDB认为查询单条数据记录远比遍历数据常见。由于B树的非叶子节点也可以存储数据，查询一条数据所需的平均随机IO次数会比B+树少，MongoDB使用B树的查询速度在类似场景下会比MySQL更快。这并不是说MongoDB不能遍历数据。我们也可以在MongoDB中使用ranges来查询一批满足相应条件的记录，但是比MySQL耗时更长。SELECT*FROMcommentsWHEREcreated_at>'2019-01-01'很多人看到遍历数据的查询，可能会想到上面显示的范围查询。不过下面这个SQL在关系型数据库中比较常见——查询外键或者字段等于某个值的所有记录：SELECT*FROMcommentsWHEREpost_id=1上面的查询不是范围查询，没有使用>,<等表达式，但是它会查询comments表中的一系列记录，如果comments表上有索引post_id，那么这个查询可能会遍历索引中对应的索引，找到符合条件的评论。此查询还将受益于MySQLB+树的互连叶节点，因为它可以减少磁盘随机性。输入输出次数。作为非关系型数据库，MongoDB在集合的设计上采用了完全不同的方法。如果我们还是用传统的关系型数据库的表设计思路来思考MongoDB中集合的设计，写类似上面这样的查询会带来比较差的性能：db.comments.find({post_id:1})因为所有节点的B树可以存储数据，没有很好的办法通过指针连接连续的节点，所以上面B-tree中的查询性能会比B+树差很多，但这在MongoDB中不是推荐的设计方式。更合适的方法是使用嵌入式文档将帖子和属于它的所有评论存储在一起：{"_id":"...","title":"WhyMongoDBusesB-tree","author":"draven","comments":[{"_id":"...","content":"你写不好这个"},{"_id":"...","content":"一楼说的对"}]}用上面的方法存储数据的时候，是不会遇到db.comments的。find({post_id:1})，我们只需要获取帖子即可获取所有相关评论。这种区别于传统关系型数据库的设计方式，需要所有使用MongoDB的开发者重新思考，这也是很多人使用MongoDB后发现性能不如MySQL的最大原因——使用姿势是错误的。这里可能有读者会有疑惑。既然MongoDB认为查询单条数据记录远比遍历数据查询更为普遍，那么为什么不使用hash作为底层数据结构呢？datastructures-and-query如果我们使用hash，那么所有单条记录查询的复杂度将是O(1)，但是遍历数据的复杂度是O(n)；如果使用B+树，那么单条记录查询的复杂度为O(logn)，遍历数据的复杂度为O(logn)+X。这两种不同的数据结构之一提供了最好的单条记录查询性能，另一个为遍历数据提供最好的性能，但是这两个都不能满足MongoDB的需求。场景——单条记录查询很常见，但是遍历数据也需要比较好的性能支持。hash这种性能极限的数据结构，只能用在简单、极端的场景。多读少写LSM树是一种基于磁盘的数据结构，其设计的主要目的是为需要长时间高频写操作的文件提供一种低成本的索引机制[^8]。不管是B-tree还是B+树，将记录写入由这些数据结构组成的索引文件都需要随机磁盘写入。LSMtree的优化逻辑是牺牲部分读性能，将随机写转化为顺序写来优化数据。写。为什么LSM树的写入性能更好，这篇文章我们不会细说，我们只是分析为什么WiredTiger默认使用B-trees作为数据结构。WiredTiger对LSM树和B树的性能进行了读写吞吐量的基准测试[^9]。通过基准测试，得到如下图所示的结果。从图中的结果我们可以发现：LSM_btree_Throughput在不限制写入的情况下；LSM树的写入性能是B树的1.5~2倍；LSM树的读取性能是B树的1/6~1/3；在有限写作的情况下；LSM树的写法与B-tree的性能基本一致；LSM-tree的读性能是B-tree的1/4~1/2；在有限写入的情况下，每秒会写入3万条数据，从这里的分析结果来看。看，在任何一种情况下，B树的读取性能都比LSM树好得多。对于大多数OLTP系统来说，系统的查询都会被多次写入，所以LSM树在写入方面的优异性能并不能使其成为MongoDB默认的数据格式。总结应用场景永远是设计系统时首先要考虑的。作为NoSQLMongoDB，它的目标场景与早期的数据库有很大的不同。下面简单总结一下MongoDB最终选择使用的两种B树。原因：MySQL使用B+树是因为数据遍历在关系型数据库中很常见。经常需要处理表之间的关系，通过范围查询一些数据；但作为一个面向文档的数据库，MongoDB与数据之间的关系相比，更注重以文档为中心的组织方式，因此选择性能更好的B树来查询单个文档。这样的选择也可以保证遍历数据的查询有一个可以接受的延迟；LSM树是一种专门针对写入的数据结构进行优化，将随机写入变为顺序写入，显着提升了写入性能，但是却以牺牲读取效率为代价，不符合大多数场景所需要的特性，所以MongoDB最终还是选择了读取性能更好的B树作为默认数据结构；最后，让我们看看一些未解决的相关问题。有兴趣的读者可以仔细思考以下问题：BigTable、LevelDB、HBase的应用场景都是什么？他们的读写比是多少？为什么要使用LSM树作为底层数据结构？在设计表结构时，MongoDB与传统关系型数据库有哪些区别？如果你对文章内容有任何疑问，或者想了解软件工程中一些设计决策背后的更多原因，可以在博客下留言，作者会及时回复与本文相关的问题，并选择合适的主题作为后续内容。[^1]：MongoDB官网现代应用的数据库https://www.mongodb.com/[^2]：分布式键值存储Dynamo实现原理https://draveness.me/dynamo[^3]：NoSQL维基百科https://en.wikipedia.org/wiki/NoSQL[^4]：NoSQL（不仅是SQL数据库）https://searchdatamanagement.techtarget.com/definition/NoSQL-Not-Only-SQL[^5]：《通俗易懂》MongoDB与WiredTigerhttps://draveness.me/mongodb-wiredtiger[^6]：MongoDB中的集合（Collection）类似于MySQL中的表（Table）[^7]：WhyMySQL使用B+树为什么是THE设计？https://draveness.me/whys-the-design-mysql-b-plus-tree[^8]：Log-StructuredMerge-Tree(LSM-Tree)，PatrickO'Neil，EdwardCheng，DieterGawlick，ElizabethO'Neilhttps://www.cs.umb.edu/~poneil/lsmtree.pdf[^9]：Btree与LSMhttps://github.com/wiredtiger/wiredtiger/wiki/Btree-vs-LSM
