Mysql索引的数据结构及索引优化

索引的本质：是帮助Mysql高效获取数据的排好序的数据结构。

索引数据结构

（1）、二叉树：存储数据的时候是一个链表，如果要查询0006的话要查询6次，如果是全表扫描的话也得查询6次。

弊端：二叉树的查询效率很低。

（2）、红黑树：存储数据的时候会自旋，如果要查询0006的话只需要查询3次。如果是全表扫描或二叉树查找的话需要6次，红黑树再二叉树的基础上查询效率提高了一半。

弊端：当数据量很大的时候（几百万或几千万），树的高度就会特别高，会存在多次磁盘IO操作影响其性能。解决以上的问题可以横向扩展，分配节点的时候分配的大一些，让其可以横向存储更多的索引元素。---- 此时B-Tree诞生了。

（3）、Hash: 对索引的key进行一次hash计算就可以定位出数据存储的位置，很多时候Hash索引要比B+树索引更高效。仅能满足“=”，“IN”，不支持范围查询。会存在hash冲突的问题。

为什么我们使用B+Tree比较多，使用hash比较少，是因为我们进行范围查询（select * from tabel where id > ***）的时候比较麻烦。

（4）、B-Tree：叶子节点具有相同的深度，叶子节点的指针为空；所有索引元素不重复；节点中的数据索引从左到右递增排列。

（5）、B+Tree(B-Tree变种)：非叶子节点不存储data，只存储索引（冗余），可以放更多的索引；叶子节点包含所有索引字段；叶子节点用指针连接，提高区间访问的性能。

下面是关于存储引擎索引的实现：

索引最左前缀原理：

案例：最左前缀法则，（排好序），根据联合索引的字段顺序排好序。由于第2、3条sql没有name,不是排好序的。需要全表扫描。