索引的本质
索引是帮助MySQL高效获取数据的排好序的数据结构
索引的数据结构
- 二叉树
- 红黑数
- Hash表
- B-Tree
MySQL索引底层为啥不用二叉树
如图，对单边增长的数据，索引效率没有什么提升
MySQL索引底层为啥不用红黑数
红黑数：二叉平衡树
随着数据的增长，数的高度会越来越高
对索引的查找效率没有什么帮助
B Tree树
- 叶节点具有相同的深度，叶子节点的指针为空
- 所有索引元素不重复
- 节点中的数据索引从左到右递增排列
B+Tree树
- 非叶子节点不存储data，只存储索引（冗余），可以放更多的索引
- 叶子节点包含所有的索引字段
B树和B+树在构建索引上，MySQL为什么最后选择了B+树？
对于树结构来说，影响索引查找效率的就是树的高度，B+树非叶子结点不存储date，只存储索引，这样的话在存储相同数据量的情况下，B+树数据结构的索引树比B树的高度更小，查询速度更快。
Hash结构
MyISAM存储引擎实现
MyISAM索引文件和数据文件是分离的（非聚集）
InnoDB索引引擎索引实现
表数据文件本身就是按照B+树组织的一个索引结构文件
聚集索引-叶子结点包含了完整的数据记录
聚集索引和非聚集索引在查找速度上那一快？
聚集索引。聚集索引查到索引后可以直接获取数据，非聚集索引在查到索引后还要跨文件获取数据。
为什么建议InnoDB表必须建主键，并且推荐使用整型的自增主键？
表数据文件需要B+树来组织索引结构文件
如果表中有主键，MySQL就会用主键来组织B+树，如果没有主键就会选择所有元素都不一样的一列来组织B+树，如果不存在，MySQL会创建一个隐藏列，来维护一个唯一id来组织B+树。
在找元素的时候是从根结点开始查找，索引定位的过程中，经历过很多次比大小，用整型比大小速度快，且整型占用内存小。
非自增时会导致叶子节点的分裂和树的自我平衡调整，影响效率。自增的话只需要往后面添加就可以了。
为什么非主键索引结构叶子节点存储的是主键值？（一致性和节省空间）
联合索引最左前缀原理
如图：联合主键索引
索引是最左前缀原理，因为是排好序的
例如：
select * from table where name = ? and age = ?
由图可知，B+树是先按照name进行排序，然后按照age排序，最后按照position进行排序。上面这个SQL语句就可以用到拍好序的索引；
select * from table where age = ? and position = ?
由于索引结构age是在name排序后再排的序，所以不通过name,直接通过age进行查找，相当于没有排序，所以不走索引。
学习数据结构的网站
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
