B-树如何让你的查询更快
内容提要
B树是现代数据库中用于高效查询的数据结构，通过自平衡特性优化数据的组织方式，提高搜索速度。与二叉搜索树不同，B树可以在单个节点中存储多个值，减少树的高度，改善搜索速度。它还使用自平衡算法在添加新值时保持平衡。B树专为在实际硬件上存储大量数据而设计。
延伸解读
B树与二叉搜索树：核心差异
B树和二叉搜索树都支持O(logn)查找，但B树在单个节点中存储多个值，从而降低树的高度。二叉搜索树每个节点只存一个值，存储大量数据时树会变得很高，导致随机访问增多。B树通过节点内多值减少树高，更适合磁盘等存储设备。
硬件访问模式对性能的影响
计算机存储分为CPU缓存、内存和磁盘。磁盘随机访问需要移动磁头，速度远慢于顺序访问。文章引用研究指出，机械硬盘上顺序访问比随机访问快几十万倍，甚至可能比内存随机读取更快。因此，数据库索引设计应尽量利用顺序访问。
B树如何优化顺序访问
B树将多个值打包到一个节点（页面）中，使树更宽更浅。查询时，每个节点只需一次随机访问加载整个页面，然后顺序读取页面内的值。例如，Postgres页面大小8KB，可存储数百个值，从而用更少的层数存储海量数据，减少随机I/O。
自平衡机制与空间权衡
B树通过自平衡算法在插入新值时保持平衡。当节点满时，会进行页分裂，将中间值提升到父节点。这种分裂可能导致页面利用率不高，但Postgres等数据库通过选择分裂点来优化。自平衡确保树始终平衡，避免性能退化。
Q&A
B树的主要特点是什么？
B树是一种自平衡的数据结构，能够在单个节点中存储多个值，从而减少树的高度，提高查询效率。
B树与二叉搜索树有什么区别？
B树可以在单个节点中存储多个值，而二叉搜索树每个节点只能存储一个值，这使得B树在处理大量数据时更高效。
B树如何优化查询速度？
B树通过减少树的高度和优化顺序访问来提高查询速度，允许在单个节点中存储多个值，从而减少随机访问的次数。
B树的自平衡特性是如何实现的？
B树通过在插入新值时使用自平衡算法，确保树的结构始终保持平衡，避免出现不平衡的情况。
B+树与B树有什么不同？
B+树是B树的变体，非叶子节点只存储键值，叶子节点之间形成有序双向链表，而B树的非叶子节点和叶子节点都存储数据。
B树在实际硬件上存储数据时的表现如何？
B树在实际硬件上表现受限于存储位置，顺序访问速度比随机访问快，尤其是在机械硬盘上，顺序访问速度快几十万倍。
