MySQL索引结构
索引（Index）是帮助MySQL高效获取数据的数据结构，在InnoDB存储引擎中，默认的索引是B+tree形式的。
InnoDB中的B+Tree索引
索引结构
- 存放数据的数据页都放在最下面一层，其他都为目录页。
- 一般用到的B+树不会超过4层，那我们通过主键值去查找某条记录最多只需要做4个页面内的查找（查找3个目录项页和一个用户记录页）。每个页面内可以通过二分法快速定位记录。假设所有存放用户记录 的叶子节点代表的数据页可以存放 100条用户记录 ，所有存放目录项记录的内节点代表的数据页可以存放1000条目录项记录 ，那么：
- 如果B+树只有1层，也就是只有1个用于存放用户记录的节点，最多能存放 100 条记录。
- 如果B+树有2层，最多能存放 1000×100=10,0000 条记录。
- 如果B+树有3层，最多能存放 1000×1000×100=1,0000,0000 条记录。
- 如果B+树有4层，最多能存放 1000×1000×1000×100=1000,0000,0000 条记录。
索引类型
聚簇索引
- 使用记录主键值的大小进行记录和页的排序
- 页内的记录是按照主键的大小顺序排成一个单向链表 。
- 各个存放数据记录的页是根据页中用户记录的主键大小顺序排成一个双向链表 。
- 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表 。
- B+树的叶子节点存储的是完整的数据记录。
- 聚簇索引将索引和数据保存在同一个B+树中，因此从聚簇索引中获取数据比非 聚簇索引更快。
- 聚簇索引对于主键的排序查找和范围查找速度非常快。
- 插入速度严重依赖于插入顺序。按照主键的顺序插入是最快的方式，否则将会出现页分裂，严重影响性能。因此，对于InnoDB表，一般都会定义一个自增的ID列为主键。
- 更新主键的代价很高。因为将会导致被更新的行移动。因此，对于InnoDB表，一般定义主键为不可更新。
- 二级索引访问需要两次索引查找。
二级索引（辅助索引、非聚簇索引）
对表中非主键字段建立的索引。
根据二级索引查找字段时，如果没有覆盖，会根据主键值到聚簇索引中再查找一遍，称为回表。
二级索引中，叶子节点存放的是该字段和其对应记录的主键值。存放的不是该记录的地址值，因为这样减少了出现行移动或者数据页分裂时二级索引的维护工作（当数据需要更新的时候，二级索引不需要修改，只需要修改聚簇索引，一个表只能有一个聚簇索引，其他的都是二级索引，这样只需要修改聚簇索引就可以了，不需要重新构建二级索引.
联合索引（属于二级索引）
- 为多个列的组合建立索引
InnoDB的B+树注意事项
根页面位置不会发生改变
当为一个表创建一个B+树索引时，都会为这个索引创建一个根节点页面。然后向表中插入数据时，先把数据记录存储到这个根节点中。当根节点可用空间用完再继续插入时，会将根节点所有记录分配到一个新的页，再对这个新页进行页分裂操作，得到另一个新页。新插入的记录根据键值大小分配到某个页中，根节点就升级为目录项存储的页。根节点常驻内存中。
内节点目录项记录唯一
在二级联合索引中，非叶子节点存放的目录项中，如果字段值相同则无法区分进入到哪个页中。所以二级索引的内节点目录项记录内容需要加上主键，即三个部分：索引列的值、主键值、页号。
一个页面至少存储两条记录
MyISAM中的索引
- MyISAM引擎使用 B+Tree 作为索引结构，叶子节点的data域存放的是数据记录的地址。
- MyISAM的索引方式都是“非聚簇”的。
- InnoDB的数据文件本身就是索引文件，而MyISAM索引文件和数据文件是分离的 ，索引文件仅保存数据记录的地址。
- InnoDB要求表必须有主键（ MyISAM可以没有 ）。如果没有显式指定，则MySQL系统会自动选择一个 可以非空且唯一标识数据记录的列作为主键。如果不存在这种列，则MySQL自动为InnoDB表生成一个隐 含字段作为主键，这个字段长度为6个字节，类型为长整型。
其它索引结构
Hash结构
- 能在O(1)时间查找，但是失去了有序行，对于order by需要排序，B+树本身查找就有序。
- 只支持精确查找，范围查找效率低。
- InnoDB 存储引擎有一个特殊的功能叫“自适应哈希索引”，当某个索引值被使用的非常频繁时，会在 B+Tree 索引之上再创建一个哈希索引，这样就让 B+Tree 索引具有哈希索引的一些优点，比如快速的哈希查找。
B树
- B树在插入和删除节点时若导致树不平衡，会自动调整保持平衡。
- 叶子节点和非叶子节点都存放数据。
- 搜索性能等价于在关键字全集做一次二分查找。
- 最下面一层并没有通过链表连接。
B+树结构较B树的优点
- B+树查询效率更稳定，因为B+树每次访问到叶子节点才会找到数据，而B树可能在非叶子节点查询到。
- B+树查询效率更高，由于B+树非叶子节点存放目录而不是数据，所以B+树更矮，查询时磁盘IO更少，同样磁盘页大小，B+树可存储更多节点关键字。
- 范围查询上，效率比B树高，因为所以关键字都在叶子节点上，叶子节点形成链表，又是非递减的。而在B树中需要通过中序遍历才能完成范围查询。