字节小喽喽
读完需要
速读仅需 1 分钟
MySQL 索引
索引的几种数据结构
哈希表。哈希表仅对键值查询时性能较好，而对于顺序查找等需求就需要根据数据的键一个个去查找，性能较差。
有序数组。有序数组在等值查询和顺序查询的方面性能都比较优秀，但是只适用于静态的数据存储，因为有序数组每插入一条新数据，都需要移动插入位置后续的数据，成本太高。
二叉树/N 叉树。因为二叉树在存储大量数据时树的高度会明显增大，而每一层数据的访问都需要经过磁盘访问，如果二叉树层数过大，访问磁盘的次数就会明显变大，性能会明显降低。如果使用 N 叉树，例如一个整数索引，在 MySQL 中这个 N 值大约是 1200，4 层这个 N 叉树就可以存储 1200 的 3 次方个数据块，已经是 10 亿量级的数据了，这种情况下访问磁盘次数最多为 3 次，很多时候数据已经在内存中了，因此访问磁盘的次数会更少。
InnoDB 的索引模型
InnoDB 使用 B+ 树作为索引的存储结构，每个索引对应一颗 B+ 树。
根据索引节点的内容，可以将 MySQL 索引分为主键索引和非主键索引。
主键索引以主键（通常为自增 ID）为 B+ 树的非叶子节点，整行数据则作为叶子结点。
非主键索引以索引建立的具体字段作为非叶子结点，表的主键作为叶子结点。
因此，如果使用非主键索引查询，如果叶子结点上只有主键的数据，而我们需要主键外的其他数据，则需要再使用该主键到主键索引中找到对应记录的主键对应叶子结点。这就是回表操作。
索引的存储需要存储空间，因此，如果主键索引的数据长度过长，那么每个非主键索引上都需要保存这个较长的主键，索引存储占用的空间就会更大。
索引有序性的维护
索引底层使用的是 B+ 树作为存储数据结构，那么就需要维护树的有序性，新记录插入的过程中，就可能发生数据页的移动或是分裂，这都会影响性能。
当然最理想的情况是插入的数据永远在 B+ 树的最后一页上，这样数据页既不用移动也不用分裂，日常使用的自增主键索引就属于这种情况。
