MySQL索引详解

如果没有索引，查询某行数据，只能进行全表扫描。这时，需要频繁地进行磁盘I/O，性能很差。索引的基本思想，就是减少一次查询所产生的磁盘I/O次数，提升查询效率。
索引一般是一个key-value结构，key是索引值。对于聚集索引(如InnoDB的主键索引)，value是该行的所有数据。对于非聚集索引(如MyISAM索引)，value是该行数据所在的磁盘块的指针。

二叉树(非平衡二叉树) 弊端：无法保证平衡性。极端情况下，可能退化成链表。此时，查询约等于全表扫描。
红黑树(平衡二叉树)
1. 优势：平衡树，不会退化成链表，相较于非平衡二叉树，查询效率有一定提升。
2. 弊端：当数据量较大时，树的高度不可控，可能导致磁盘IO次数较多，效率下降。
3. 优化思路：让一个树的节点存储更多的索引元素，从而降低树的高度。
B树

特性：
1. 树的每个节点，存储多个索引元素，同时存储索引对应的数据。
2. 叶节点具有相同的深度，叶节点的指针为空。
3. 所有索引元素不重复。
4. 节点中的数据索引从左到右递增排列。
弊端：
1. 树的所有节点(包括叶子节点和非叶子节点)都同时存储索引和数据，导致每个索引元素所占空间较大。当树的节点空间一定时，每个节点保存的索引元素数量就较少，最终导致树的高度较高。
2. 树的每个节点的大小是固定的，一般为一页(Page)16KB。可通过命令查看： show global status like ‘Innodb_page_size’;
优化思路：尽可能减少每个索引元素所占的空间大小，使得每个树节点可以存储更多的索引元素，从而减小树的高度。
B+树

特性：
1. 非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引。
2. 叶子节点包含所有索引字段和对应的数据。
3. 节点中的数据索引从左到右递增排列。
4. 叶子节点用双向指针连接，提高区间访问的性能。
优势：
1. 树高度较矮，针对大多数的表，2~4层即可满足需求。
2. 区间访问性能较好。

存储引擎的粒度是表级别的。同一个数据库下的不同表，可以使用不同的存储引擎。

MyISAM为聚集索引，索引文件和数据文件分离，索引数据保存的是对应行所在的磁盘文件指针。
MyISAM使用3个文件保存数据：
1. .frm：保存表的定义、结构等元信息。
2. .MYD：保存表中的所有数据行。
3. .MYI：保存表中的所有索引字段。
InnoDB引擎

在 InnoDB 中，表都是根据主键的顺序，以索引的形式存放的，这种存储方式的表称为索引组织表。
InnoDB 的主键索引为聚集索引，索引的叶子节点保存的是该行的所有数据。
InnoDB 使用2个文件保存数据：
1. .frm：保存表的定义、结构等元信息。
2. .ibd：同时保存InnoDB的数据和索引。
对于主键索引，叶子节点的内容是所在行的所有数据。在 InnoDB 里，主键索引也被称为聚簇索引（clustered index）。
对于非主键索引，叶子节点的内容是主键的值。在 InnoDB 里，非主键索引也被称为二级索引（secondary index）。
基于非主键索引的查询时，需要根据查询到的主键值，再去主键索引查询一次记录，这个过程称为回表。回表会导致多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。

为什么 InnoDB 表必须有主键，且推荐整型的自增主键？ ** InnoDB 的表数据文件(.ibd)，就是按照B+树结构，根据主键索引组织起来的一个索引结构文件，因此一定要有一个主键。如果用户没有自定义主键，InnoDB会选择一列唯一索引作为主键。如果没有唯一索引，InnoDB 会为每行数据生成一个唯一的整型自增数值rowId(隐藏列)，作为主键来组织整个索引文件。** 使用整型主键，索引查询时，比较效率较高。且整型字段所占空间较小。 使用自增主键，大部分的插入操作，都是在叶子节点链表上的addLast，不会涉及到节点的页分裂和整棵树的平衡操作，插入效率很高。
为什么 InnoDB 的的非主键索引，存储的是主键索引的值，而不是像主键索引一样直接存储数据？
1. 数据一致性角度：如果数据在多个索引处维护，那么就存在数据一致性问题。插入一条记录时，需要在每个索引树上都插入一遍，就涉及到了分布式事务的问题。
2. 存储空间角度：如果所有索引树都保存数据，会造成大量的空间浪费。
在 InnoDB 引擎下，重建主键索引，无论是新增还是删除，都会导致整张表进行重建。可以使用 alter table T engine=InnoDB 来重建主键索引。