应用程序处理的数据量持续增长。数据的增长对存储容量的扩展提出了挑战。每个数据库管理系统在这方面都有自己的权衡。了解这些权衡取舍对于数据管理员来说至关重要，这样才能在各种方法中做出正确的选择。应用程序在读/写工作负载平衡、一致性需求、延迟和访问模式方面各不相同。如果我们能够了解数据库和存储内部设施的架构决策，将有助于我们了解系统行为的原因，在问题发生时解决问题，并根据工作负载调整数据库。一个系统不可能在所有方面都是完美的。保证没有存储开销并且提供最佳读写性能的数据结构只存在于理想情况下，当然在实践中是不可能存在的。本文详细分析了大多数现代数据库使用的两种存储系统设计方法，即为读优化的B-tree1和为写优化的LSM（log-structuredmerge）tree5，并给出了一些用例和权衡考虑这两种方法。1.B-treeB-tree是一种应用广泛的读优化索引数据结构，是二叉树的推广。它有多个变体，并已用于多个数据库（包括MySQLInnoDB4和PostgreSQL7）和文件系统（例如HFS+8、ext4中的HTrees9）。B树中的“B”是“拜耳”的意思，指的是数据结构的最初创始人鲁道夫·拜耳，或者拜耳当时供职的波音公司。在二叉树中，每个节点都有两个孩子（分别称为左孩子和右孩子）。左子树和右子树中存储的键（Key），其值分别小于和大于当前节点的键。为了保持树的最小深度，二叉树必须是平衡的。当以随机顺序向树中添加键时，很自然地会导致树的一侧比另一侧更深。一种重新平衡二叉树的方法称为“旋转”方法。rotate方法实现了节点的重新排列，将更深的子树的父节点下推到其子节点下方，并将子节点向上移动，有效地将父节点放置在其原始位置。图1给出了一个实现二叉树平衡的旋转方法示例。添加节点“2”后左侧的二叉树不平衡。为了平衡二叉树，我们围绕节点“3”旋转树，然后围绕节点“5”旋转。节点“5”是原始根节点，是节点“3”的父节点。轮换后成为节点“3”的子节点。旋转完成后得到右边的树，其中左子树的深度减1，右子树的深度加1，树的最大深度减少。图1示例：使用旋转方法平衡二叉树二叉树是一种非常有用的内存数据结构。由于二叉树的平衡（即需要将所有子树的深度保持在最低限度）和低扇出（每个节点最多有两个指针）属性，二叉树在磁盘上表现不佳。B树允许每个节点存储两个以上的指针，并且可以调整节点大小以适合一个页面（例如4KB），因此在块设备上运行良好。目前，有些实现使用更大的节点，甚至跨多个页面。B数据具有以下属性：排序：排序支持顺序扫描，简化查找。自平衡：插入和删除操作不需要重新平衡树。一个B-tree节点满了之后，会分裂成两个节点。如果两个相邻节点的占用率低于某个阈值，则合并节点。这意味着每个叶子节点与根节点的距离相等，搜索时可以使用相同的步数进行定位。查找操作具有对数时间复杂度保证。这使得B树成为查找时间至关重要的数据库索引的不错选择。支持可变数据结构。插入、更新和删除（以及后续的节点拆分和合并）都是在磁盘上进行的，实现深度更新需要一定的空间开销。B树可以组织为聚簇索引，将实际数据存储在叶节点上，或者使用非聚簇索引，将数据存储为堆文件。本文还介绍了B+树3.B+树是B树的变种，常用于数据库存储。B+树与原始B树相比，不同之处在于：1、B+树的叶子节点存储值，形成一个额外的链接层。2、B+树的内部结点不存值。B树剖析让我们仔细看看B树的构建块，如图2所示。B树有多种节点类型，包括根节点、内部节点和叶节点。根节点（顶部）是没有父节点的节点（即它不是任何其他节点的子节点）。内部节点（中间）有连接根节点和叶节点的父节点和子节点。叶节点（底部）保存数据，它没有子节点。图2是一个B树，分支因子为4，即4个指针，内部节点3个键值对，叶子节点4个键值对。图2示例：B-tree标识一个B-tree，可以使用以下指标：分支因子：指向子节点的指针的个数（N）。考虑到指针的存在，根节点和内部节点可以存储N-1个键值。Utilizationrate：可用指针数中，当前有多少指向子项的指针被使用。例如，如果树的分支因子为N，并且节点当前持有N/2个指针，则利用率为50%。height：B树的层数，表示查找要遍历的指针个数。树中的每个非叶子节点最多持有N个键（索引项），将树分裂成N+1个子树，可以用相应的指针定位。在条目Ki中指针i指向的子树中，所有索引条目都是Ki-1<=Ksearched
