定义
索引
- 索引本质是对数据的简化（由地址值代替真实值）排序，索引自身不小，也就不可能全部存储在内存中，因此索引 也通常以索引文件的形式存储在磁盘中
- 其次，索引为了维持自身指向的有效性，也要随真实数据的增删改发生改变（无效数据，新增数据，越来越臃肿） 也就是——索引查询会随数据量增加变的越来越慢
- 最后，仍是因为维持索引的有效性，那么就会在真实数据更新操作的同时更新索引指向，故此索引会降低更新效率
索引优劣
好处：
- 提高数据查找速度，减少磁盘IO/次数
- 通过索引来对数据排序。降低查询时 OrderBy 子句对 CPU 消耗，提高 OrderBy 子句 的查询速度
坏处：
- 索引 实际上也是个表，存储 唯一主键 、字段值别值、真实字段值地址，所以 索引 也会占用 内存磁盘资源
- 索引 提升查询速度，同时也会降低更新表速度。（更新 真实数据的同时也要更新索引表）
- 索引 不可能为每个字段及其他们的所有组合都建立一个索引，故此，就要花时间研究建立 最有效索引 或 优化索引
B树
每个节点不仅包含节点key值，还有其他额外数据。非叶子节点包含三部分数据,内存中可能不连续
- 指针,指向下一个节点地址的指针
- 当前树key值，一般为索引元素当前值
- 包含真实数据的地址(磁盘地址)
B+树
- 非叶节点只存储key值和指向下一级的指针
- 叶子节点存储相应数据(对于聚集索引来说:存储了主键及其他数据行值，对于非聚集索引来说，存储的是主键的值，然后通过 回表操作，查询聚集索引，获取完整数据,所谓的回表，就是先通过二级索引查询主键值，然后通过聚集索引查询全部值)
Mysql为何使用B+树作为索引
- B+树的磁盘读写代价更低: B+树的内部节点并没有指向关键字具体信息的指针，因此其内部节点相对B树更小， 如果把所有同一内部节点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多，一次性读入内存的 需要查找的关键字也就越多，相对IO读写次数就降低了。
- B+树的查询效率更加稳定: B+树非叶子节点不存储数据，要想获取到真实数据，每次查询都必须走一遍从根节点 到叶节点的路。所有查询路径长度相同，效率相当。
- B+树更便于遍历: B+树只有叶子节点存储数据，所以只需要便利一遍叶子节点即可。而B树，则需要中序便利一次 才能获取。
- B+树更适合基于范围的查询: 树在提高了IO性能的同时并没有解决元素遍历的我效率低下的问题，正是为了解决这 个问题，B+树应用而生。B+树只需要去遍历叶子节点就可以实现整棵树的遍历(叶子节点拥有指向下一个节点的指针)。而且在数据库中基于范围的查询是非常 频繁的，而B树不支持这样的操作或者说效率太低。
MyISAM和InnoDB
聚集索引：
MyISAM索引文件和数据文件是分离的，索引文件仅保存记录所在页的指针（物理位置），通过这些地址来读取页，进而读取被索引的行。即，MyISAM采用B+ 树建立索引，叶子节点存储的是真实记录的物理地址。然后通过此物理地址，在data文件中查询具体的值
与 MyISAM相同的一点是，InnoDB 也采用 B+Tree这种数据结构来实现 B-Tree索引。而很大的区别在于，InnoDB 存储引擎采用“聚集索引”的数据存储 方式实现B-Tree索引，所谓“聚集”，就是指数据行和相邻的键值紧凑地存储在一起，注意 InnoDB 只能聚集一个叶子页（16K）的记录（即聚集索引满足一定的范围的记录），因此包含相邻键值的记录可能会相距甚远
对于innodb:
- 主键索引 既存储索引值,又在叶子中存储行的数据
- 如果没有主键, 则会Unique key做主键
- 如果没有unique,则系统生成一个内部的rowid做主键.
- 像innodb中,主键的索引结构中,既存储了主键值,又存储了行数据,这种结构称为”聚簇索引”
辅助索引:
而对于辅助索引，InnoDB采用的方式是在叶子页中保存主键值，通过这个主键值来回表（上图）查询到一条完整记录， 因此按辅助索引检索实际上进行了二次查询，效率肯定是没有按照主键检索高的。
于每个辅助索引都包含主键索引，因此，为了减小辅助索引所占空间，我们通常希望 InnoDB 表中的主键索引尽量定义得小一些 （值得一提的是，MySIAM会使用前缀压缩技术使得索引变小，而InnoDB按照原数据格式进行存储。），并且希望InnoDB的主键是 自增长的，因为如果主键并非自增长，插入时，由于写入时乱序的，会使得插入效率变低