Mysql索引底层数据结构与算法

一.索引概述
是什么:
索引是帮助MySQL高效获取数据的排好序的数据结构,索引叫"键",优化好一个索引,可以提高数倍的性能, 类似于字典的音序表
为什么要键索引:
目的在于提高查询效率,通过不断的缩小要获取数据的范围来筛选最终的结果,把随机的事件变为顺序事件.
二.索引数据结构
1.二叉树
二叉树是一种非线性结构。只有一个根节点，每一个数据结点上最多只有左右两颗子树.它有五种基本形态：二叉树可以是空集；根可以有空的左子树或右子树；活着左、右子树皆为空。

2.红黑树
红黑树解决了二叉查找树多次插入新节点可能导致的不平衡问题,红黑树是一种自平衡的二叉查找树

3.Hash
是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度.这个映射函数称做散列
函数，存放记录的数组称做散列表。哈希表（Hash Table）其实也叫散列表.哈希表可以用来高效率解决元素不可重复这个问题，其本质就是：数组+链表+红黑树

4.B-Tree
是一种平衡的多路查找树.叶节点具有相同的深度，叶节点的指针为空,所有索引元素不重复,节点中的数据索引从左到右递增排列

5.B+Tree(B-Tree变种)
是常用于数据库和操作系统的文件系统中的一种用于查找的数据结构, 是对b树的优化.非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引.叶子节点包含所有索引字段.叶子节点用指针
连接，提高区间,随着数据量变大,主要是控制树的高度才能提高效率
访问的性能

6.mysql索引选择
Mysql索引可以选hash和b+树, hash比b+树运算块, 但是现在公司主要用b+树, 因为hash对范围查找不支持,只是支持等值查找，还存在hash冲突问题。b+树有双向指针,更好的支持范围查找。

三.存储引擎索引实现
1.MyISAM索引文件和数据文件是分离的(非聚集)

2.InnoDB索引实现(聚集)
表数据文件本身就是按B+Tree组织的一个索引结构文件
聚集索引-叶节点包含了完整的数据记录
为什么建议InnoDB表必须建主键，并且推荐使用整型的自增主键？
为什么非主键索引结构叶子节点存储的是主键值？(一致性和节省存储空间)

四.索引最左前缀原理
在mysql建立联合索引时会遵循最左前缀匹配的原则，即最左优先，在检索数据时从联合索引的最左边开始匹配