参考： https://juejin.cn/post/7412893752090181642?from=search-suggest

Mysql为什么选择B+树作为索引结构？

1. 减少磁盘I/O次数
   • B+树每个节点可以存储大量键值，使得树的高度极低
   • 数据库数据存储在磁盘上，每次查询磁盘I/O次数直接影响性能，B+树通过降低树的高度，显著减少了I/O次数
2. 高效范围查询：
   • 叶子节点链表结构： B+树的所有数据存储在叶子节点，而且叶子节点之间通过指针有序连接
   • 范围扫描优化：对于WHERE age > 20 AND age < 30这类查询，B+树只需要定位到起始点后便利链表即可，而B树需要复杂的中序遍历

对比其它数据结构

哈希表： 苏日安哈希索引的等值查询是O(1)，但是无法支持范围查询和排序

二叉搜索树： 树高过高，会导致多次磁盘IO，且可能退化成链表

B树： B树的非叶子节点存储数据，导致单个节点能容纳的键值更少，树高更高。

B树范围查询需要回溯父节点，B+树通过叶子链表直接便利。

转载自：

https://github.com/0voice/newsql_nosql_library/blob/main/mysql/存储引擎/B+树原理详解.md

B+树原理详解

B+树是B树的一种变体，有着比B树更高的查询性能。一个m阶B树具有如下特征：

1. 根节点至少有两个节点；
2. 每个中间节点都包含k-1个元素和k个孩子，其中m/2<=k<=m；
3. 每一个叶子节点都包含k-1个元素，其中m/2<=k<=m；
4. 所有的叶子节点都位于同一层；
5. 每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域划分。

B+树和B树有一些共同特征，但是B+树也具备一些新的特征：

1. 有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点；
2. 所有的叶子节点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子节点本身依关键字的大小自小而大顺序链接；
3. 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

我们具体来看一下B+树结构：