随着应用程序处理的数据量不断增加，扩展存储变得越来越具有挑战性。每个数据库系统都有自己的方案。为了从这些选项中做出正确的选择，了解它们至关重要。每个应用程序在读写负载平衡、一致性、延迟和访问模式方面都是不同的。熟悉数据库和底层存储可以帮助您根据具体情况做出架构决策、解释系统行为、故障排除和调整。优化系统并不能解决所有问题。当然，我们希望有一种数据结构，既能保证最好的读写性能，又不产生任何存储开销，但很显然，这是不存在的。本文深入讨论了大多数现代数据库中使用的两种存储系统设计——读取优化的B-Tree[1]和写入优化的LSM（日志结构合并）-Tree[5]——并描述了它们的使用案例和优缺点。B-TreeB-Tree是一种流行的读优化索引数据结构，是二叉树的推广。它有许多变体，用于许多数据库（包括MySQLInnoDB[4]、PostgreSQL[7]）甚至文件系统（HFS+[8]、HTreesext4[9]）。B-Tree中的B代表Bayer，原始数据结构的作者，或者他当时工作的公司，波音公司。在搜索二叉树时，每个节点都有两个孩子（称为左孩子和右孩子）。左子树节点值小于当前节点值，右子树节点值小于当前节点值。为了使树的深度保持最小，搜索二叉树必须是平衡的：当值以随机顺序添加到树中时，如果不进行调整，最终会导致树的倾斜。平衡二叉树的一种方法是所谓的旋转：重新排列节点，将更深子树的父节点向下推到其子节点下方，并将该子节点向上拉，将其放在原始父节点的位置。图1是平衡二叉树中的旋转示例。在左侧添加节点2后，二叉树变得不平衡。要平衡树，请围绕节点3旋转它（树围绕它旋转）。然后节点5（在旋转之前是根节点和节点3的父节点）成为它的子节点。旋转完成后，左子树的深度减1，右子树的深度增加1，树的最大深度已经减少。二叉树是最有用的内存数据结构。然而，由于平衡（将所有子树的深度保持在最低限度）和低出度（每个节点最多有两个孩子），它们不太适合磁盘。B-Tree允许每个节点存储两个以上的指针，并通过将节点大小与页面大小（例如4KB）相匹配来使用块设备。今天的一些实现将使用更大的节点大小，跨越多个页面。B-Tree具有以下属性：?有序。这允许顺序扫描并简化查找。?自平衡。不需要在插入和删除上平衡树：当B-Tree节点满时，将其一分为二，当相邻节点的利用率低于某个阈值时，合并两个节点。这也意味着每个叶节点到根节点的距离是相等的，搜索过程的步数是相同的。?对数搜索时间复杂度。查找时间非常重要，这使得B-Tree成为数据库索引的理想选择。?易挥发的。插入、更新、删除（包括由此产生的拆分和合并）在磁盘上执行。为了使就地更新成为可能，需要一定量的空间开销。B-Tree可以作为聚集索引，实际数据存放在叶子节点上，也可以作为非聚集索引，称为堆文件。本文中讨论的B+Tree[3]是B-Tree的现代变体，通常用于数据库存储。B+Tree与原始B-Tree[1]的不同之处在于：(1)它使用额外链接的叶节点来存储值；(2)值不能存储在内部节点上。分析B-Tree让我们仔细看看B-Tree的结构，如图2所示。B-Tree中有几种类型的节点：根节点、内部节点和叶节点。根节点（顶部）是没有父节点的节点（即，它不是任何节点的子节点）。内部节点（中间）有父节点和子节点；它们连接根节点和叶节点。叶节点（底部）保存数据并且没有子节点。图2描绘了一个B树，其分支因子为4（4个指针，内部节点中有3个键，叶子上有4个键/值对）。B树的属性如下：?分支因子——指向子节点的指针数(N)。除了指针，根节点和内部节点还持有N-1个密钥。?利用率——一个节点当前持有的指向子节点的指针数量与可用值的比率。例如，如果树的分支因子为N，并且其中一个节点当前持有N/2个指针，则节点利用率为50%。?高度——B-Tree的大小，表示在搜索过程中必须传递多少个指针。树中的每个非叶子节点最多可以容纳N个键（索引条目），这些键将树划分为N+1个子树，这些子树可以通过相应的指针定位。条目Ki中的指针i指向包含所有索引条目的子树，其中Ki-1<=Ktarget
