B-树如何让你的查询更快
💡
原文中文，约4500字，阅读约需11分钟。
📝
内容提要
B树是现代数据库中用于高效查询的数据结构，通过自平衡特性优化数据的组织方式，提高搜索速度。与二叉搜索树不同，B树可以在单个节点中存储多个值，减少树的高度，改善搜索速度。它还使用自平衡算法在添加新值时保持平衡。B树专为在实际硬件上存储大量数据而设计。
🎯
关键要点
- B树是一种高效查询的数据结构，具有自平衡特性，优化数据组织方式。
- B树与二叉搜索树不同，可以在单个节点中存储多个值，减少树的高度。
- B树专为在实际硬件上存储大量数据而设计，仍然是现代数据库中常用的索引结构。
- B树的B代表的含义与二叉搜索树的混淆是一个常见误解。
- B树的查找时间复杂度为O(logn)，但在实际硬件上表现受限于存储位置。
- 计算机存储数据的三个位置为CPU缓存、RAM和磁盘，随机访问和顺序访问的速度差异显著。
- 顺序访问在机械硬盘上的速度比随机访问快几十万倍，固态硬盘的表现也在不断提升。
- 通过将多个值打包到一个节点中，B树可以减少高度，优化顺序访问。
- B树的自平衡特性确保在插入新值时保持树的平衡，避免不平衡树的出现。
- B树的节点可以存储多个值，减少树的高度，从而提高查询效率。
- B+树是B树的变体，非叶子节点只存储键值，叶子节点之间形成有序双向链表。
- B树和B+树之间的关系是B+树是B树的特例，二者在数据存储结构上存在差异。
➡️
