B+Tree作为索引数据结构的优势

B+Tree vs B Tree

1. B+Tree 只在叶子节点存储数据，而B树的非叶子节点也要存储数据，所以 B+Tree的非叶子节点可以存储更多的索引信息。
2. 另外，B+Tree 叶子节点采用的是双链表连接，适合 MySQL 中常见的基于范围的顺序查找，而 B 树无法做到这一点。

B+Tree vs 二叉树

由于树是存储在磁盘中的，访问每个节点，都对应一次磁盘 I/O 操作，也就是说树的高度就等于每次查询数据时磁盘 IO 操作的次数，所以树的高度越高，就会影响查询性能。

树允许的子节点越多，树的高度就越矮，对应的磁盘 I/O 次数就更少。

对于有 N 个叶子节点的 B+Tree，其搜索复杂度为O(logdN)，其中 d 表示节点允许的最大子节点个数为 d 个。

在实际的应用当中， d 值是大于100的，这样就保证了，即使数据达到千万级别时，B+Tree 的高度依然维持在 34 层左右，也就是说一次数据查询操作只需要做 34 次的磁盘 I/O 操作就能查询到目标数据。

而二叉树的每个父节点的子节点个数只能是 2 个，意味着其搜索复杂度为 O(logN)，且树结构更高经历的磁盘 I/O 次数要更多。

B+Tree vs Hash

Hash 在做等值查询的时候效率贼快，搜索复杂度为 O(1)。

但是 Hash 表不适合做范围查询，它更适合做等值的查询，这也是 B+Tree 索引要比 Hash 表索引有着更广泛的适用场景的原因。