索引数据结构
MySQL中常见索引数据有B+Tree、Hash，其他几乎不用。
Hash
最简单，容易理解，其实用的也不多，因为有局限性
优点：
- 一次内存运算即可定位，效率高
缺点：
- 有可能hash冲突，这就会导致定位后拿到一个链表再进行遍历；
- 不适用于范围查找，仅用于“=”、“IN”
B+Tree
默认的索引数据结构
优点：
- 层级少，定位效率高
- 支持所有sql条件查询
缺点：
- 非范围/排序类效率较Hash差
B+Tree仅在叶子节点上会存储数据（非主键索引叶子节点存储对应主键索引地址），其他非叶子节点仅是索引。这就是相对于BTree的改进，在非叶子节点上能够存储更多的索引（MySQL默认每页存储空间应该是16K）。
这里以主键索引为例，假设主键为bigint，那非叶子节点每页可存储索引数为16K/×8+6），约等于1170，如果设置B+Tree为3层（两层非叶子节点+一层叶子节点），那两层非叶子节点就可存储近137万条索引，如果设置3层非叶子节点那就可以存储16亿条索引了。
别忘了还有一层叶子节点，假设每个叶子节点的数据都占用1K存储，那每页叶子节点就可以存16条数据。
B+Tree层级 | 存储数据量 |
3 | 2190万 |
4 | 256亿 |
如果换成BTree要达到过两千万的存储，需要有7层，这效率就立马下来了。