适用于只有等值查询的场景，Memory引擎默认索引
InnoDB支持自适应哈希索引，不可干预，由引擎自行决定是否创建
有序数组：在等值查询和范围查询场景中的性能都非常优秀，但插入和删除数据需要进行数据移动，成本太高。因此，只适用于静态存储引擎
二叉平衡树：每个节点的左儿子小于父节点，父节点又小于右儿子，时间复杂度是 O(log(N))
多叉平衡树：索引不止存在内存中，还要写到磁盘上。为了让一个查询尽量少地读磁盘，就必须让查询过程访问尽量少的数据块。因此，要使用“N 叉”树。
B+TreeB-Tree 与 B+Tree
B-Tree
B+Tree
InnoDB 使用了 B+ 树索引模型。假设，我们有一个主键列为 ID 的表，表中有字段 k，并且在 k 上有索引，如下所示：
主键索引：也被称为聚簇索引，叶子节点存的是整行数据
非主键索引：也被称为二级索引，叶子节点内容是主键的值
注意事项
索引基于数据页有序存储，可能发生数据页的分裂(页存储空间不足)和合并(数据删除造成页利用率低)
数据的无序插入会造成数据的移动，甚至数据页的分裂
主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小
索引字段越小，单层可存储数据量越多，可减少磁盘IO
// 假设一个数据页16K、一行数据1K、索引间指针6字节、索引字段bigint类型(8字节) // 索引个数 K = 16*1024/(8+6) =1170 // 单个叶子节点记录数 N = 16/1 = 16 // 三层B+记录数 V = K*K*N = 21902400MyISAM也是使用B+Tree索引，区别在于不区分主键和非主键索引，均是非聚簇索引，叶子节点保存的是数据文件的指针
索引选择优化器选择索引的目的，是找到一个最优的执行方案，并用最小的代价去执行语句。在数据库里面，扫描行数是影响执行代价的因素之一。扫描的行数越少，意味着访问磁盘数据的次数越少，消耗的 CPU 资源越少。
当然，扫描行数并不是唯一的判断标准，优化器还会结合是否使用临时表、是否排序等因素进行综合判断。
扫描行数如何计算
一个索引上不同的值越多，这个索引的区分度就越好。而一个索引上不同的值的个数，称之为“基数”（cardinality）。
-- 查看当前索引基数 mysql> show index from test; +-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+ | Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment | +-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+ | test | 0 | PRIMARY | 1 | id | A | 100256 | NULL | NULL | | BTREE | | | | test | 1 | index_a | 1 | a | A | 98199 | NULL | NULL | YES | BTREE | | | +-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+从性能的角度考虑，InnoDB 使用采样统计，默认会选择 N 个数据页，统计这些页面上的不同值，得到一个平均值，然后乘以这个索引的页面数，就得到了这个索引的基数。因此，上述两个索引显示的基数并不相同。
而数据表是会持续更新的，索引统计信息也不会固定不变。所以，当变更的数据行数超过 1/M 的时候(innodb_stats_persistent=on时默认10，反之16)，会自动触发重新做一次索引统计。
mysql> show variables like '%innodb_stats_persistent%'; +--------------------------------------+-------------+ | Variable_name | Value | +--------------------------------------+-------------+ -- 是否自动触发更新统计信息，当被修改的数据超过10%时就会触发统计信息重新统计计算 | innodb_stats_auto_recalc | ON | -- 控制在重新计算统计信息时是否会考虑删除标记的记录 | innodb_stats_include_delete_marked | OFF | -- 对null值的统计方法，当变量设置为nulls_equal时，所有NULL值都被视为相同 | innodb_stats_method | nulls_equal | -- 操作元数据时是否触发更新统计信息 | innodb_stats_on_metadata | OFF | -- 统计信息是否持久化存储 | innodb_stats_persistent | ON | -- innodb_stats_persistent=on，持久化统计信息采样的抽样页数 | innodb_stats_persistent_sample_pages | 20 | -- 不推荐使用，已经被innodb_stats_transient_sample_pages替换 | innodb_stats_sample_pages | 8 | -- 瞬时抽样page数 | innodb_stats_transient_sample_pages | 8 | +--------------------------------------+-------------+