innodb为什么用b+树
InnoDB 选择 B+树作为其默认索引结构，是经过深思熟虑的，主要因为它完美契合了数据库管理系统（尤其是面向磁盘存储的系统）的核心需求，即高效地管理存储在慢速磁盘上的海量数据。以下是详细原因：
极高的扇出度（Fanout）与矮胖的树结构：
B+树的一个关键特性是它的非叶子节点只存储键值（Key）和指向子节点的指针（Child Pointer），不存储实际的数据行（Row Data）。
这意味着单个磁盘页（InnoDB 默认为 16KB）可以容纳非常多的键值和指针。计算一下：一个键值（如 BIGINT 主键）8字节，一个指针（页号）6字节，那么一页大约可以存储
16KB / (8B + 6B) ≈ 1170个键值-指针对。这种极高的扇出度使得 B+树在存储海量数据时能保持非常矮的树高。一个 3 层的 B+树就能存储
1170 * 1170 * 1170 ≈ 16亿个键值对（假设叶子节点也存 1170 条记录）。实际叶子节点存储数据行，容量会小一些（比如每页存几十到几百行），但三层树支持千万级到亿级数据量是轻而易举的。优点： 树矮意味着从根节点查找到任意叶子节点所需的磁盘 I/O 次数非常少（通常 3-4 次）。磁盘 I/O 是数据库操作中最慢的操作，极大影响性能。减少 I/O 次数是数据库索引设计的首要目标。
所有数据存储在叶子节点，且叶子节点有序链表连接：
数据位置： 在 B+树中，所有实际的数据行（或指向数据行的指针）都只存储在叶子节点中。非叶子节点仅作为索引导航。
叶子链表： 所有叶子节点通过双向指针（或单向指针）按顺序连接成一个有序链表。
优点：
高效的范围查询： 这是 B+树相对于 B 树最显著的优势之一。要查询某个范围（如
WHERE id BETWEEN 100 AND 500），只需定位到范围起始点（id=100）所在的叶子节点，然后沿着叶子节点的链表顺序扫描即可，直到超出范围（id>500）。这种顺序访问非常高效，利用了磁盘的顺序读取特性（比随机读取快得多）。全表扫描高效： 遍历整个表只需从链表头扫描到链表尾，同样高效。
查询路径长度一致： 无论查找哪个键值，路径长度都等于树高（因为必须走到叶子节点）。这使得查询性能更可预测（稳定在 O(log n)），而 B 树可能在非叶子节点就找到数据，导致查询时间有波动。
更有效的磁盘预读：
数据库系统和操作系统会利用局部性原理进行磁盘预读（Read-Ahead）。当读取一个磁盘页时，其相邻的页也可能被预先加载到内存中。
B+树的范围查询和全表扫描需要顺序访问叶子节点，这种访问模式完美匹配磁盘预读策略，能显著提升连续数据块的读取效率
更优的空间局部性（针对索引本身）：
由于非叶子节点只存储键和指针，不存储数据，它们可以容纳更多的条目。这使得在非叶子节点层进行查找时，一次磁盘 I/O 能加载更多有效的索引信息（更多的键值比较信息），提高了缓存的效率，进一步减少了定位目标叶子节点所需的 I/O 次数。
更适合基于页的存储管理：
InnoDB 使用固定大小的页（Page）作为磁盘和内存之间数据传输的基本单位（默认 16KB）。B+树的节点设计（尤其是非叶子节点）可以非常自然地填充整个页或页的一部分，最大限度地利用一次磁盘 I/O 读取的数据量。
为什么不是其他数据结构？
二叉树/二叉搜索树（BST）： 树高太高（O(n) 最坏，O(log n) 平均但不平衡），I/O 次数太多。无法有效利用磁盘块。极易退化成链表。
平衡二叉树（AVL/红黑树）： 解决了平衡问题，树高 O(log n)，但每个节点最多只有 2 个子节点，扇出度太低。存储海量数据时树高仍然非常高（比如 1 亿数据需要约 27 次比较，意味着可能 27 次磁盘 I/O），效率远低于 B+树（3-4 次 I/O）。
B树： B 树允许非叶子节点存储数据。这导致：
非叶子节点能存储的键值-指针对变少（因为空间被数据占用），扇出度降低，树高增加。
范围查询效率低： 数据分散在树的各层，进行范围查询时需要在中层节点和叶子节点之间来回跳跃（回溯），效率远不如 B+树叶子节点的顺序扫描。
哈希索引：
优点： 等值查询（
=）速度极快，理论 O(1)。致命缺点： 完全不支持范围查询（
>,<,BETWEEN,LIKE 'prefix%'）、排序（ORDER BY）、分组（GROUP BY）以及最左前缀匹配。这些操作对数据库至关重要。哈希冲突处理也可能影响性能。因此，InnoDB 支持自适应哈希索引，但这只是对内存中热点数据的 B+树索引的补充优化，并非主要磁盘索引结构。
跳表（Skip List）： 内存中效率不错，但不太适合直接映射到磁盘上的页式管理。范围查询效率不如 B+树叶子链表直接。在磁盘持久化场景下，B+树的结构更成熟、更优化。
总结：
InnoDB 选择 B+树作为索引结构的核心原因在于它完美地平衡了磁盘 I/O 效率、范围查询性能和树的管理复杂度：
极矮的树高： 通过非叶子节点不存数据实现高扇出度，大幅减少查询所需的磁盘 I/O 次数（核心目标）。
高效的范围查询： 所有数据存储在有序链表连接的叶子节点中，顺序扫描极其高效。
稳定的查询性能： 任何查询都从根到叶子节点，路径长度一致。
利用磁盘特性： 节点大小匹配磁盘页，顺序访问利用预读。
支持全表扫描： 通过叶子链表高效完成。
B+树的设计哲学就是：最大化每次磁盘 I/O 获取的信息量（高扇出度），最小化访问次数（矮树高），并为最常见的数据库操作（范围查询、排序）提供最优访问模式（有序叶子链表）。这使得它成为基于磁盘的关系型数据库索引的黄金标准。