案例库 · 工程与运营 · 技术决策 · 1970–1972
B树让数据库索引从内存转向磁盘
1972年，Bayer和McCreight将每个树节点扩大为一个磁盘块，使查找几乎无需寻道。
波音科学研究所
那一手
任何大型有序索引都会大到无法装入主内存，因此部分必须放在磁盘上，而磁盘寻道远比任何计算都昂贵。二叉搜索树是自然选择，但它很高，查找一个键需要每一层一次寻道，这在规模化时是灾难性的。
Bayer和McCreight的B树扭转了这一点。节点大小等于一个磁盘块，容纳多个键和多个子节点，因此下降一层就能跨越大量数据。所有叶子位于同一深度，节点保持最小和最大填充率之间，因此树保持平衡，只需偶尔分裂。
效果是，无论索引增长多大，查找触及的块数几乎恒定且很少。这正是数据库或文件系统在索引超出内存后仍然可用的关键。
为什么管用
- 将每个节点设为磁盘块大小，意味着一次寻道可同时获取许多键。
- 保持树浅且叶子同深，避免了高二叉树的多次寻道开销。
- 允许每个节点有多个子节点，使树的重平衡频率大大降低。
值了多少让每个节点容纳一个完整的磁盘页面聪明
可以搬走什么
当昂贵的资源是访问而非计算时，围绕它重新设计结构：将一个宽节点做成磁盘块，使一次寻道能完成大量工作，并保持每次查找的成本很低。
后来呢
B树成为数据库和文件系统的标准索引结构，几乎所有关系数据库以及文件系统、键值存储都使用它；其平衡性和块大小的节点设计，使得即使在千兆级数据上查找也只需少数几次磁盘读取。
资料来源
发现哪里写错了？告诉我们。