索引是帮助mysql高效获取数据的排好序的数据结构
为什么数据结构不是二叉树？
因为mysql数据存储在硬盘中，每次插入数据都会读写硬盘数据，二叉树原则是右边比父节点大，左边比父节点小，如果索引建立在自增ID上，查找ID为10w的数据，会查找10w次，查询效率慢。
为什么数据结构不使用红黑树？
红黑树又叫平衡二叉树，是一种二叉树的扩展，在数据量大的情况下依旧无法承载索引所需要提供的查询效率，从根节点会一直找到对应的叶子节点。
B-Tree
叶节点具有相同的深度，叶节点的指针为空
所有索引元素不重复
节点中的数据索引从左到右递增排列
mysql 在内存中默认分配16kb内存，存储节点
B-Tree一个节点占用1kb 一行只可以存储16个?
B+Tree
非叶子节点不存储data，只存储索引，可以放更多索引
叶子节点包含所有索引字段
叶子节点用指针链接，提高区间访问性能
每行可以放 1024kb/(8+6)b的数据
树的高度越小，查询效率越快，所以选用B+Tree，BTree中叶子节点没有用指针链接，如果查询范围数据的话效率远不如B+Tree 如 age>50。
?
Hash
?缺点不支持范围查询
MyISAM存储引擎索引实现
存储到硬盘的文件
frm 表结构信息
MYD文件 MyISAM引擎Data文件??
MYI文件 MyISAM引擎Index文件
Index文件存储格式?
在Index文件中查找到对应的文件地址去Data文件中读取数据 找到指定数据
InnoDB存储引擎索引实现
?
?frm 表结构信息
ibd 包含索引和数据信息
表数据文件本身就按B+Tree组织的一个索引结构文件
聚集索引-叶节点包含了完整的数据记录
?为什么InnoDB表必须建主键，并推荐使用整型的自增主键？
因为如果没有建立自增主键，mysql会查找一列不重复的数据建立B+Tree索引，如果没有符合该规则的列则会建立一列隐藏列来建立索引。
如果使用字符串类型，例如UUID，会降低性能，B+Tree数据会从小到大依次排序，字符串类型使用ASCII码顺序来进行对比，性能远不及整型。
由于每次插入时也不需要移动已有数据，因此效率很高，也不会增加很多开销在维护索引上
如果使用非自增主键（如果身份证号或学号等），由于每次插入主键的值近似于随机，因此每次新纪录都要被插到现有索引页得中间某个位置，此时MySQL不得不为了将新记录插到合适位置而移动数据，甚至目标页面可能已经被回写到磁盘上而从缓存中清掉，此时又要从磁盘上读回来，这增加了很多开销，同时频繁的移动、分页操作造成了大量的碎片，得到了不够紧凑的索引结构，后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。
为什么非主键索引结构叶子节点存储的是主键值？
?一致性和节省存储空间
属于非聚簇索引，找到对应的主键之后去到聚簇索引中查找对应的数据
一个表只会有一个聚簇索引
联合索引
索引最左前缀原理
?索引的原则是排好序，根据排序去查找对应的数据，它会根据字段的顺序去依次排序，如果直接查找第二个，索引会进行全表扫描，排序规则不会生效
?