Mysql各种索引结构的优劣

二叉树

结构简单，大的值放右边，小的值放左边，对散列值存储优势大，能达到log2n，但是在顺序值上面，存在缺陷，会导致结构退化成链表

二叉树

退化的二叉树

红黑树

红黑树是 二叉平横树，每次插入大的值时，会自旋转一下，调整树结构，相比二叉树，没有退化成链表结构，但是红黑树在大数据的时候，会存在树层数过多（高度过高）的问题，Mysql的红黑树通过增大节点存储的索引个数来减少高度。也就是B树

红黑树

Mysql红黑树

B树

特点:

1. 叶子节点具有相同的高度，叶子节点的指针为空，非叶子节点才有data值
2. 所有索引元素不重复
3. 节点中的数据索引从左到右递增排列
4. Mysql也没有采用这种方式，而是优化后的B+树

B树

B+树

1. 和B树相反，叶子节点才存储data，非叶子节点不存储data
2. 叶子节点也是从左到右递增排列
3. 叶子节点包含所有索引字段
4. 叶子节点用指针相链，提高区间访问性能
5. Mysql每个节点默认设置大小是16kb
6. 默认高度为3，高度3可以放2000万个索引节点
7. 查找流程，每个节点用折半查找，找到下一个节点，继续折半，最终找到对应索引

B+树