现代分布式存储系统的算法

在读写负载平衡、一致性、延迟和访问模式方面各不相同。熟悉数据库和底层存储能帮助你进行架构决策、解释系统行为、排除故障以及根据具体情况调优。

优化一个系统不可能做到面面俱到。我们当然希望有一个数据结构既能保证最佳的读写性能，又不需要任何存储开销，但显然，这是不存在的。

本文深入讨论了大多数现代数据库中使用的两种存储系统设计 —— 读优化 B-Tree [1] 和写优化 LSM(log-structured merge)-Tree [5] —— 并描述了它们的用例和优缺权衡。

B-Tree

B-Tree 是一种流行的读优化索引数据结构，是二叉树的泛化。它有许多变种，并且被用于多种数据库(包括 MySQL InnoDB [4]、PostgreSQL [7])甚至文件系统(HFS+ [8]、HTrees ext4 [9])。B-Tree 中的 B 代表原始数据结构的作者 Bayer，或是他当时就职的公司 Boeing。

在搜索二叉树中，每个节点都有两个孩子(称为左右孩子)。左子树的节点值小于当前节点值，右子树反之。为了保持树的深度最小，搜索二叉树必须是平衡的：当随机顺序的值被添加到树中时，如果不加调整，终会导致树的倾斜。

一种平衡二叉树的方法是所谓的旋转：重新排列节点，将较深子树的父节点向下推到其子节点下方，并将该子节点拉上来，将其放在原父节点的位置。图 1 是平衡二叉树中的旋转示例。在左侧添加节点 2 后，二叉树失去平衡。为了使该树平衡，将其以节点 3 为轴旋转(树围绕它旋转)。然后节点 5(旋转前是根节点和节点 3 的父节点)成为其子节点。旋转完成后，左侧子树的深度减少 1，右侧子树的深度增加 1。树的最大深度已经减小。

（编辑：广元站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!