索引是帮组MySQL高效获取数据的排好序的数据结构
索引数据结构：
二叉树， 红黑树，Hash表，B-Tree

树结构分析：

https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

二叉树：

image.png
面对递增的数据，二叉树会单边增长，变成链表
image.png

红黑树：

平衡二叉树，插入数据的时候有一个自旋平衡的过程
JDK1.8及以后的版本中引入了红黑树结构，HashMap的实现就变成了数组+链表（长度为8）或数组+红黑树
image.png
MySQL没有采用红黑树，主要因为树的高度不能控住，如果数据量为一百万，树的高度为二十，如果查找的数据在叶子节点，就需要二十次的磁盘IO才能找到

hash表：

一次索引即可查出数据，性能非常高，但是不能用于范围查询的情况，所以运用的场景少
image.png
image.png

B-树：

image.png
一个大节点上面存储了很多索引小元素 解决了红黑树的高度问题，子节点没有指针，还是没有解决范围查找

B+树：

image.png
MySQL对B+树节点大小设置为16K
SHOW GLOBAL STATUS LIKE ‘Innobd_page_size’;
用bigInteger（8B+指针6B） 每个节点可存1170个索引元素，叶子节点data算1kB，高度为3的B+树，也可以存储
1170117010个数据（二千万）
叶子节点之间有指针
MySQL会把根节点存储到内存，只需要两次磁盘IO，即可查找到需要的数据