索引是帮助mysql高效获取数据的排好序的数据结构
1.二叉树
2.红黑树
3.hash表
4.b树
二叉树
依次递增 每插入一行先维护我们的索引数
因为二叉树的特点就是 插入大的元素它永远往右下角插入 逐渐往链表方向靠近
在递增的列字段上面会退化成链表
红黑树
也可以被叫做平衡二叉树
它比二叉树多出了平衡性 也就是当树的一边比另一边高时会自动进行平衡
但是为什么不用红黑树而转为使用b树呢
因为如果数据量增大 如果我们要查询的数据刚好在底层的叶节点 我们还是将逐步遍历叶节点
所以由于叶节点的不稳定性 红黑树作为索引的效率还是不算太高
也就是说 红黑树的缺点就是 数据过大时 树的高度不太可控
hash表（数组+链表）
对索引的key进行一次hash计算就可以定位出数据存储位置
hash冲突问题
不用hash的原因：不支持范围查询
b树
也是由红黑树演变过来
但是节点中的数据索引是从左到右递增的 所有的索引元素不重复
叶节点具有相同的深度，叶节点的指针为空
b+树
是由b树优化过来的
非叶子节点不会存储date date就是索引那一行磁盘文件地址 只存储索引 可以放更多索引
叶子节点包含所有索引字段
叶子节点用指针连接 可以提升区间访问的性能
如何在b+树中查找一个元素
假设我们要查找一个最底层叶节点的元素
从根节点开始查询 从左到右依次递增
会加载到ram中再进行一个折半查找后到叶节点
mysql对b+树节点设置了大小 一页大概16kb
一页除以一个索引加一个指针（8+6）b 根节点大概可以放1170个索引 叶子节点大概可以放两千多万的索引元素
数据库的存储引擎
MYISAM ,InnoDB
使用索引结构的差别
对事务的支持不同
锁的粒度不同
对于全文检索的支持不同
效率不同，MyISAM的效率要高一点
MyISAM不支持外键，而 InnoDB是唯一支持外键的MySQL引擎
聚集索引和非聚集索引
MYISAM索引文件是和数据文件是分离的（非聚集）
InnoDB索引实现（聚集）
表数据文件本身就是按B+tree组织的一个索引文件
聚集索引-叶子节点包含完整的数据记录
为什么建议innodb表必须建主键 并且推荐使用整型的自增主键
不建主键索引维护整张表的数据 会浪费性能
为什么推荐使用整型的自增主键
可能会导致插入元素时当时节点元素分裂
B+树结构
页的使用
在MySQL的InnoDb引擎中，页的大小是16KB，是操作系统的4倍，而int类型的数据是4个字节，其它类型的数据的字节数通常也在4000字节以内，所以一页是可以存放很多很多条数据的，而MySQL的数据正是以页为基本单位组合而成的。
优势：页能够通过在查询某条数据时，将一页的数据存入内存而不是一行，减少磁盘io次数。
页目录
页目录 就是说 我们查询页中 会使用页进行排序 但是如果要更快的进行查询元素
我们应该是要增加一个查询元素的目录 也就是说 类似于元素的集合 当然使用页排序是建立页目录的前提
多页模式
当我们数据过大时 使用一个页是远远不够的
就将采用开辟新页的方式将多条数据放在不同的页中
然后使用指针相连
覆盖索引
覆盖索引就是从辅助（非主键）索引中就能直接得到查询结果，而不需要回表到聚簇索引中进行再次查询，所以可以减少
搜索次数（不需要从辅助索引树回表到聚簇索引树），或者说减少IO操作（通过辅助索引树可以一次性从磁盘
载入更多节点），从而提升性能。
联合索引
需要加索引的字段，要在where条件中
数据量少的字段不需要加索引
如果where条件中是OR关系，加索引不起作用
符合最左原则
联合索引是指对表上的多个列进行索引
联合索引的排序
经常用的列优先（最左匹配原则）
离散度高的列优先（离散度高原则）
宽度小的列优先（最少空间原则）