为什么mysql索引使用B+Tree数据结构
以100万条数据为例：
- 红黑树：红黑树是放在内存的，多次磁盘IO导致性能降低
- 哈希索引：哈希值是无序，不能进行范围查找
- AVL：随着高度的增加，查找的速度变慢，范围查找虽然可以查，但是很慢，因为要回旋
- B-Tree:解决了AVL高度太高的问题，一个节点存多个数据，所以它的查找速度很快，但范围查找的回旋问题没有解决
- B+Tree:在B-Tree的基础上解决了回旋查找的问题，叶子节点是一个双向链表，这样范围查找很快。mysql索引使用B+Tree，索引放在磁盘上。
B+Tree
B+Tree的性质:
- 每个节点最多有m个子节点
- 除根节点外，每个节点至少有m/2个子节点，注意如果结果除不尽，就向上取整，比如5/2=3.
- 根节点要么是空，要么是独根，否则至少有2个子节点
- 有k个子节点的节点必有k个关键码
- 叶节点的高度一致
- M:页大小4k/字段的大小，所以索引的字段类型要小，这样性能才高
mysql联合索引使用最左匹配原则，也就是说查询语句第一个查询如果查的是索引，那么就走索引，如果不是索引，那么查询类型就是all(全表查询)，或者index(遍历索引)。
视频链接:
阿里总监求放过，我再也不嘚瑟了，MySQL索引数据结构为什么使用B+树，我来告诉你
2021最新数据结构与算法/红黑树/B+树/Hash算法/暴力算法全网最完整版
