1.索引数据结构红黑树，Hash,B+树详解
索引的本质
描述:索引是帮助Mysql高效获取数据的排好序的数据结构
索引数据结构分类
1.二叉树
特点:左边小右边大于等于父节点
缺点：如果插入自增长索引，一直单边增长，对查询没有意义，如下图
2.红黑树
特点：自动保持平衡
缺点:楼层太高，查询次数过多，维护复杂
3.Hash表
特点：对索引值进行hash运算，得到磁盘文件指针，查询where index=1的等值预算的时候性能非常高
缺点：空间能力差，做范围查询where index>1的时候不好做索引
4.B-Tree
叶节点具有相同的深度，叶节点的指针为空
所有索引元素不重复
节点中的数据索引从左到右递增排列
对比:比红黑树楼层低，查询效率高
缺点：每个索引对应一个值，导致索引占用空间太大
B+Tree(MySql底层采用B+Tree数据结构)
特点：非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引
叶子节点包含所有索引字段
叶子节点用指针连接，提高区间访问的性能
2.索引是怎么支撑千万级表的快速查找
一个索引(8B)加上一个指针(6B),mysql允许最大值为16kb,16kb/(6B+8B)=1170个分叉，所以最后结果为1170*1170*16=21902400两千多万
3.面试常问B+树索引面试题解析
Mysql存储引擎：
1.MyISAM(非聚集索引)
文件：.frm 存储数据结构 .MYD存储数据记录.MYI存储索引
查询方式:根据索引查找内存空间指针，再根据空间指针再MYD文件查找记录
2.InnerDB（聚集索引）
文件：.frm 存储数据结构 .idb数据和索引存在一起
查询方式:根据索引直接查找数据
提问：聚集索引和非聚集索引区别
答:非聚集索引是通过空间指正查找MYD文件查询到的数据，聚集索引是因为索引和数据存储在一起，每一条记录前面都有个索引，可以直接通过索引取数据
提问：为什么InnoDB表必须有主键，并且推荐使用整型的自增主键？
答：InnoDB就是这样设计的，通过主键索引构建B+Tree；整形比较大小比字符串比较大小更快更高效，例如比较1<2比a>b更高效，字符串比较还要转换asci,自增是不用打破原来的B+Tree，直接再后面加数据，如果不是，可能需要重新元素分裂平衡
提问：为什么非主键索引结构叶子节点存储的是主键值？
答：一致性和节省存储空间，所有的非主键索引最后定位到的是主键索引，然后再通过主键索引查找数据，换而言之，就是差了两次树，非主键索引定位到主键索引，这样节省了存储空间，如果建了多个非主键索引，我就要保存多个记录，如果非主键索引做了修改，主键索引没有，这样就导致了数据不一致，但是如果非主键索引最后定位到主键索引，通过主键索引查找数据，这样就保持了一致性
4.联合索引底层数据结构又是怎样的
和主键索引类似，不过是有多个字段组成
