索引是什么？
索引是高效获取数据的数据结构。
索引可以是hash的，可以是B+Tree的，hash索引存放在内存中，B+Tree存放在硬盘中
自适应hash索引（innodb引擎）
数据量大时内存占用大；只支持等值查询；对范围查询和排序支持不好。
哪种存储引擎支持手动hash索引？
memory，因为它将数据放在内存中。适合做中间表
AVL树为什么不能做索引的存储结构？
数据量大会导致树变深，增加查询IO次数；每个节点关键字只有一个，每次IO拿到数据太少（pagesize=16kb）
BTree为什么不做索引的存储结构？
最多关键字个数=路数-1
每个节点三部分：关键字，数据区，子节点指针。数据区理解为数据存储在磁盘中的位置，相当于磁盘指针
瘦高的树变为矮胖的树，减少IO次数，节点关键字变多，每次IO拿到的数据变多
B+Tree为什么作为索引存储结构？
基于索引排序和范围查找能力更强；基于索引的扫库扫表能力更强；查询时间稳定；取消了数据区使读写能力更强
B+Tree怎么存储？
都存在硬盘中，但myisam和innodb存储引擎有差别
myisam引擎有myd和myi文件，一个存放索引，一个存放数据。无论是主键索引还是非主键索引，都是查询到叶子节点，
叶子节点中存放的是磁盘指针，根据指针值在myd文件中获取具体内容。
innodb引擎中只有ibd文件，叶子节点直接挂载的是真正的行记录，根据主键查到后直接返回行记录。非主键索引的叶子节点存放的是索引列的值和主键的值。
根据非主键索引查到主键id，再根据主键ID找到行记录
聚集索引和非聚集索引
innodb引擎中，只有主键是聚集索引，其他都是非聚集索引
手动建立主键索引的好处
列的离散型
对离散型好的列建立索引，因为计算机在BTree中能清楚的知道走那一路，如果用离散型不好的列，例如sex建立索引，计算机不知道走哪一路，会都不走，变成无效索引联合索引
例如name+phone+age联合索引，相当于建立了三列的索引: name, name+phone, name+phone+age 是从左到右建立搜索树的。
原文：https://www.cnblogs.com/staff/p/13175019.html