mysql索引数据机构
1、索引数据结构：二叉树、红黑树、hash表、B-TREE
二叉树：缺点：退化成链表的情况
红黑树：如果发现单边增长的态势，会自旋转自动平衡，缺点：高度，加入数据量100万，红黑树的高度就2的n次方了。太高了，查找的元素若在叶子节点，那么查找需要的磁盘io次数也很多，慢的很；
hash表：
也就是对某个列的值进行hash运算，只要一次查找就可以从hash表中找到对应的指针，因此而找到数据
hash表中存放，索引hash值,磁盘文件指针；
缺点：范围索引的时候，没辙了
B树：mysql中索引90%都会选B树，每一个节点能存储更多的数据，相对于红黑树来讲，横向扩展了，高度控制在一定范围了
那将多有的索引放到一个节点不可以吗？不行，这样数据量大，一次磁盘io，全部放到内存中，也慢的很；B树的一个节点存储大小大约是16k;
单纯的b树还是解决不了范围查找
B+树：所有的数据在叶子节点有一份完整的数据；非叶子节点不存储数据；为什么如此设计？
B+树的一个节点存储大小大也是16k;因为非叶子节点不存储数据，那么就可以存储更多的索引
B+树，磁盘io相当少
B+树的高度有限制吗？有一般3就达到了几千万数据，再多的话，就涉及分库分表了；
范围查找的问题解决看图，因为有指针？是的
2、聚集索引：innodb的主键索引就是聚集索引 （聚集的是数据文件和索引文件）,叶子节点包含了完整的数据
mylsam的数据存储模式就是非聚集索引 (分离的是数据文件和索引文件）
3、innodb必须要有主键，如果没有建的话，底层会针对每列生成一个唯一的key，没有这个唯一的key，B+树数据结构无法阻止
为什么主键需要自增？？使用uuid的案例是错误的，uuid相比较于整型来说，占用存储空间更大；B+树有比较大小的机制，叶子节点从左到右一次递增，但是uuid比较大小费劲
而且，非递增的时候，生成红黑树分裂也比较严重，因此效率低下
4、联合索引底层
联合索引的存储架构图，所有字段排个序，最左匹配原则