B+树是什么？

B+树是1970 年Rudolf Bayer 教授在Organization and Maintenance of Large Ordered Indices 一文中提出的。如今已经成为最为常见，也是在数据库中使用最为频繁的一种索引结构。它基于可变存储方式，能够快速地根据键值找到数据行所在的页。B+树采用多叉树结构，降低了索引结构的深度，避免传统二叉树结构中绝大部分的随机访问操作，从而有效地减少了磁盘磁头的寻道次数，降低了外存访问延迟对性能的影响。它保证树节点中键值对的有序性，从而控制查询、插入、删除和更新操作的时间复杂度在O(logn) 的范围内。鉴于上述优势，B+树作为索引结构的构建模块，被广泛应用在大量数据库系统和存储系统中，其中就包括PolarDB、MySQL 等云原生数据库。

以上内容摘自《云原生数据库原理与实践》，这本书可以在电子工业出版社天猫店购买。