索引 - 《两汉书姓名韵》

小雷  |  2019. 08. 10   |  阅读 321 次
MySQL Node.js 数据 服务端

索引一词最早出现于西方,主要是中世纪欧洲宗教著作的索引。明末傅山所编的《两汉书姓名韵》是中国现存最早的人名索引。

前言

其实,索引对大家而言并不陌生,自己在日常开发中也经常接触,但让自己真正把它说清楚,深入浅出的讲明白也会语塞,为了突破只会发音拼写的阶段,理清索引背后的一些细节,于是就有了本文。

正文

先简要介绍下索引,顾名思义,它如书的目录一般,通过目录查找比用整本书一页页的查找快得多,从而能快速的帮你定位查找的内容。在 MySQL 中,索引是对数据表进行排序的数据结构,能在查询时帮你减少磁盘 io 的次数,从而提升你的查询性能。

在平时日常开发建表时,一般都会添加一个主键字段:id,而 MySQL 默认会给主键建了索引,称为主键索引,不允许重复,不允许空值。这里涉及到了索引的分类,一般常见的分类有:主键索引、唯一索引、普通索引、全文索引、组合索引:

  • 主键索引:即主索引,根据主键 pk_clolum(length)建立索引,不允许重复,不允许空值;

    ALTER TABLE 'tablename' ADD PRIMARY KEY pkindex('col');

  • 唯一索引:用来建立索引的列的值必须是唯一的,允许空值;

    ALTER TABLE 'tablename' ADD UNIQUE indexname('col');

  • 普通索引:用表中的普通列构建的索引,没有任何限制;

    ALTER TABLE 'tablename' ADD INDEX indexname('col');

  • 全文索引:用大文本对象的列构建的索引;

    ALTER TABLE 'tablename' ADD FULLTEXT INDEX ftindex('col');

  • 组合索引:用多个列组合构建的索引,这多个列中的值不允许有空值;

    ALTER TABLE 'tablename' ADD INDEX indexname('col1','col2','col3');

简单了解了索引分类后,那这个索引是怎么存储的呢?这就和索引存储结构(也有叫存储方法)有关。一般建索引时,存储结构有 BTREEHASH 两个选项,默认是 BTREE,下面是两者的一些区别:

BTREE

BTREE 是平衡搜索多叉树,本质上是一种二叉树结构的变种,能够解决不平衡导致的查询性能问题。一般存储设备解决二叉树平衡问题采取平衡多路查找树(B-Tree)B+TreeB+Tree 是在 B-Tree 基础上的一种优化,使其更适合实现外存储索引结构,这里的 BTREE 就是指 B+tree

HASH

基于哈希表实现,只有精确匹配到索引列的查询,才会起到效果。对于每一行数据,存储引擎都会对所有的索引列计算出一个哈希码(hash code),然后在hash code 相应的位置存执该值所在行数据的物理位置,所以,HASH 索引比较的是进行 hash 运算之后的 hash 值,即等值的过滤。因为使用散列算法,因此访问速度非常快,也使得查询效率比 BTREE 更高。

两者的区别在于:

  • 只有 memory 存储引擎支持 HASH 索引。
  • HASH 索引等值过滤的特性使得它只能满足 =, IN<=> 查询,不能使用范围查询。
  • HASH 索引,hash 运算后值的大小关系并非和运算前的键值完全一样,使得它不支持排序操作,运算前后值关系不一的原因也使得每次都得扫描实际表数据后才能得出最终结果。
  • 由于树结构的查询特性,一般情况下 BTREE 结构的查询会比 HASH 索引低,但如果 Hash 索引遇到大量 hash 值相等的情况后性能并不一定就会比 BTREE 索引高。

由于 HASH 索引这些局限,所以日常使用较频繁的是 BTREE 索引,也是为什么索引结构默认都是 BTREE 索引;

OK,那我们也就知道了主键索引是按 BTREE 结构存储的,那这个 MySQL 具体是怎么实现的呢?

我们知道现在建表默认存储引擎是 InnoDB 引擎(v5.5.5 开始),而不同存储引擎的实现是不一样的,这里介绍常见的两种存储引擎 MyISAMInnoDB 在实现存储结构上的区别。

MyISAM

我们约定主键索引为主索引,而其他的字段的索引为辅助索引,他们的叶子结点的key 都存储指向键值对应的数据的物理地址,只是主索引不允许重复,不允许空值,所以数据表和索引表是分开存储的。所以,这种索引顺序是与数据物理排列顺序无关的,我们称为非聚簇索引

InnoDB

InnoDB 的主索引的叶子结点存储的是键值对应的数据本身,辅助索引的叶子结点存储的是键值对应的数据的主键键值,所以,主键的值越小越好,越小所占磁盘空间越小。

因为辅助索引存的是主键值,所以像普通查询(select * ...)的查询条件是非主键索引的话,需要先在辅助索引树上得到主键,然后再到主键索引树上查询一次。这个过程即平时提到的回表,故应该尽量减少回表操作,即减少磁盘 io 的次数,加快了查询速度。像这种索引的顺序为数据的物理存储顺序,我们称为聚簇索引,所以上文的主键索引也称为聚簇索引,这里的辅助索引也称为二级索引

下图可以形象的体现这两者的区别: alt

平时,我们经常提到索引会影响写入性能,就是因为写入时,除了存储数据本身,还要维护索引树。比如,插入一条记录,如果指定 ID 的话,若 ID 值比表里最大的 ID 要大,则只需要追加一个新纪录即可,比较麻烦的是如果 ID 值小于表里的最大值,则为了保持数据有序,需要挪动后面的数据,空出空间。MySQL 是以一定大小的数据页为单位来组织数据的,麻烦的是,如果挪动所在的数据页已经满了,则需要申请新的数据页,然后挪动部分数据过去,这个过程称为页分裂,这种情况会更影响性能。页分裂使得原本一个页的数据分到了两页,整体空间率会降低,MySQL 为了提升利用率,会将相邻两个利用率很低的数据页进行合并,即称为页合并

这也是为什么,会建议建表时给主键设置自增,这样插入时可以不指定 ID,系统会直接追加一条记录,不会导致挪动其他记录和页分裂的情况。

总结

本文主要剖析了索引的一些实现原理细节,介绍了索引分类,索引存储结构,存储引擎对其的实现原理以及索引维护,希望能加深大家对索引的理解。如果想了解具体查询的索引命中情况,也可戳 explain 让你的 sql 写的更踏实

参考

分享到

   
尴尬而不失优雅地实现移动端响应式布局
加入我们