发布时间：2021-08-17 09:32:47 阅读次数：183
如果没有索引，查询某行数据，只能进行全表扫描。这时，需要频繁地进行磁盘I/O，性能很差。索引的基本思想，就是减少一次查询所产生的磁盘I/O次数，提升查询效率。
索引一般是一个key-value结构，key是索引值。 对于聚集索引(如InnoDB的主键索引)，value是该行的所有数据。 对于非聚集索引(如MyISAM索引)，value是该行数据所在的磁盘块的指针。
二叉树(非平衡二叉树) 弊端：无法保证平衡性。极端情况下，可能退化成链表。此时，查询约等于全表扫描。
红黑树(平衡二叉树)
优势：平衡树，不会退化成链表，相较于非平衡二叉树，查询效率有一定提升。
弊端：当数据量较大时，树的高度不可控，可能导致磁盘IO次数较多，效率下降。
优化思路：让一个树的节点存储更多的索引元素，从而降低树的高度。
B树
特性：
树的每个节点，存储多个索引元素，同时存储索引对应的数据。
叶节点具有相同的深度，叶节点的指针为空。
所有索引元素不重复。
节点中的数据索引从左到右递增排列。
弊端：
树的所有节点(包括叶子节点和非叶子节点)都同时存储索引和数据，导致每个索引元素所占空间较大。当树的节点空间一定时，每个节点保存的索引元素数量就较少，最终导致树的高度较高。
树的每个节点的大小是固定的，一般为一页(Page)16KB。可通过命令查看： show global status like ‘Innodb_page_size’;
优化思路：尽可能减少每个索引元素所占的空间大小，使得每个树节点可以存储更多的索引元素，从而减小树的高度。
B+树
特性：
非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引。
叶子节点包含所有索引字段和对应的数据。
节点中的数据索引从左到右递增排列。
叶子节点用双向指针连接，提高区间访问的性能。
优势：
树高度较矮，针对大多数的表，2~4层即可满足需求。
区间访问性能较好。
Hash
特性：对索引值进行hash，映射成对应数据行所在的磁盘文件指针。
弊端：
不支持范围查询。
不支持模糊查询。
不支持排序。
哈希冲突问题。
适用场景：大量等值查询时。
存储引擎的粒度是表级别的。同一个数据库下的不同表，可以使用不同的存储引擎。
MyISAM引擎
MyISAM为聚集索引，索引文件和数据文件分离，索引数据保存的是对应行所在的磁盘文件指针。
MyISAM使用3个文件保存数据：
.frm：保存表的定义、结构等元信息。
.MYD：保存表中的所有数据行。
.MYI：保存表中的所有索引字段。
InnoDB引擎
在 InnoDB 中，表都是根据主键的顺序，以索引的形式存放的，这种存储方式的表称为索引组织表。
InnoDB 的主键索引为聚集索引，索引的叶子节点保存的是该行的所有数据。
InnoDB 使用2个文件保存数据：
.frm：保存表的定义、结构等元信息。
.ibd：同时保存InnoDB的数据和索引。
对于主键索引，叶子节点的内容是所在行的所有数据。在 InnoDB 里，主键索引也被称为聚簇索引（clustered index）。
对于非主键索引，叶子节点的内容是主键的值。在 InnoDB 里，非主键索引也被称为二级索引（secondary index）。
基于非主键索引的查询时，需要根据查询到的主键值，再去主键索引查询一次记录，这个过程称为回表。回表会导致多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。
