索引的常见构造方式
实现索引的途径有多种，下面先介绍三种常见的结构：哈希表、有序数组以及搜索树。
哈希表：仅适用于仅有等值查询的场景。
有序数组：在等值查询和范围查询场景下性能都很不错，但在更新数据时需要移动大量记录，所以只适用于静态存储引擎。
二叉搜索树：树的层数可能会比较高，要是一个节点上的数据在一个物理数据块里，那么访问叶子节点的数据就会产生大量磁盘IO。
为了让一次查询尽可能少地进行磁盘IO，会用N叉树来替代二叉树。
到目前数据库技术发展来看，跳表、LSM树等结构也被应用到引擎设计中。得清楚数据库底层存储的核心是基于数据模型的，所以每遇到一个新数据库，得先关注它的数据模型，这样才能从理论上分析出这个数据库的适用场景。
InnoDB的索引构造
在InnoDB中，表都是按照主键顺序以索引的形式存储的。由于InnoDB采用了B+树索引模型，所以数据都存储在B+树里。
每一个索引在InnoDB中对应着一棵B+树。
依据叶子节点的内容，索引类型分为主键索引和非主键索引：
-
主键索引的叶子节点存储的是整行数据。在InnoDB中，主键索引也被称作聚簇索引。
-
非主键索引的叶子节点存储的是主键的值。在InnoDB中，非主键索引也被称作二级索引。
对于非主键索引，假如执行select *查询，那么得先查询非主键的索引树，得到主键后再查询一次，这个过程叫做回表。所以，应该尽量使用主键来查询。
索引维护
B+树为了维持索引的有序性，在插入新值的时候需要进行必要的维护。要是插入时所在的数据页已满，按照B+树的算法，这时候得申请一个新的数据页，然后挪动部分数据过去，这个过程叫做页分裂，会对性能产生较大影响。同时，页分裂还会影响数据页的利用率，原本放在一个页的数据，分到两个页中，整体空间利用率大概会降低50%。
页分裂的逆过程是页合并。当相邻两个页因为删除了数据，利用率很低之后，会把数据页进行合并。
基于索引维护，来探讨哪些场景应该使用自增主键，哪些情况不应该用。
当设置了自增主键，插入的时候可以不指定主键值，而且插入符合递增插入，每次插入都是一次追加操作，不会挪动其他记录，也不会触发叶子节点的分裂。而用有业务逻辑的字段做主键，往往没法保证有序插入，这样就可能出现页分裂。
除了考虑性能，从存储空间的角度来看，自增主键的字节数通常也比较小，那么普通索引的叶子节点就会更小，占用的空间也会更少。
所以，从性能和存储空间方面考虑，自增主键往往是更合理的选择。而有些业务场景，比如要求只有一个唯一索引，那么该索引列自然就作为主键了。
文章整理自互联网，只做测试使用。发布者：Lomu，转转请注明出处：https://www.it1024doc.com/13065.html
