数据库_B-Tree_索引为何统治半世纪

提供的文章是一篇深入的技术探讨，解释了 B-树（或 B+树） 成为 MySQL 和 PostgreSQL 等基于磁盘的数据库系统索引标准的原因。文章开篇指出，传统的 二叉搜索树（BST） 由于扇出率低，在磁盘上进行查询时会导致大量的输入/输出（I/O）操作，性能极其低下。B-树通过将节点大小与 磁盘块大小 匹配来实现高效性，从而确保了 高扇出率，极大程度地减少了树的高度。这种设计使得对数十亿条记录的查找只需要进行少数几次 磁盘寻址，从而将查询时间从数百毫秒降低至毫秒级。作者详细分析了 B-树的结构、自动平衡机制（分裂与合并），并探讨了其在现实世界数据库中的应用，以及如 写入放大 等局限性。