目录

• 前言
• 索引

• 索引罕用模型

  • 哈希表
  • 有序数组
  • 均衡二叉树
• InnoDB 索引模型
• 主键索引和一般索引
• 页决裂和页合并
• 主键为什么倡议抉择自增主键？

前言

当提到 mysql 数据库时，脑海里本能反馈蹦出几个关键词：数据结构(B+ 树)、索引、事务、锁、日志等等，明天就来说一说索引那些事儿，我会把索引分为高低两集来进行论述。

可能你理解 mysql 索引底层采纳数据结构 B + 树实现的，在某个字段中建设索引，会放慢查问效率，然而在面试中是远远不够的，在这里，先抛出几个对于索引的面试题：

• 索引为什么应用 B + 树，而不应用 B 树，二叉搜寻树？
• 那些数据结构能够作为索引？他们的优缺点是什么？
• 一般索引和主键索引的区别？
• 汇集索引和非汇集索引的区别？
• 索引什么时候会生效，最左匹配准则是什么？
• 索引下推理解吗？
• 谈一谈你对回表的了解，能够举个例子吗？
• 主键为什么倡议应用自增主键？
• 页决裂和页合并

这几个面试题都会在索引这两集中一一揭晓。
第一个面试题，我在上篇文章就解答了(https://mp.weixin.qq.com/s/1sy-jLCuWgpci-56vxdiLA)

索引

一句话简略的来说，索引的呈现就是为了放慢数据库的查问效率，就好比书的目录一样。

举个生存中的例子，在你眼前有一本 500 页的书籍，如果你想要查找某个知识点，在没有目录的状况下，你可能须要一页一页翻书查找；如果这本数据有目录性能，你只需在目录上找到对应知识点的页数即可，效率大幅度提高。同样 mysql 也是，索引就是他的 ” 目录 ”。

索引常见模型

索引的呈现为了放慢数据库的查问效率，然而索引的实现有多种形式，比方 哈希表 、 有序数组 、 搜寻树 、B+ 树。这几种数据结构比较简单但又是面试常问的问题，心愿重点关注一下。上面
我会去介绍一下这几个数据结构，他们的优缺点是什么。

哈希表

哈希表是对于键值对 (key-value) 存储的数据结构，应用起来比较简单，咱们只须要输出特定的 key 值就可找到对应的 value 值。实现起来也比较简单，通过哈希函数把 key 值转换成一个固定的值，作为桶位，而后将 value 值存储在该桶位下。

但应用哈希表作为索引数据结构的话，存在一个问题，多个 key 通过哈希函数的换算，会呈现同一值的状况。解决这种状况，就是在某个桶位上拉出链表进行实现，构造如下所示：

因而应用哈希表作为索引存储构造，比拟实用于只有等值查问的场景。比方 Memcached 及其他一些 NoSQL 引擎。

有序数组

有序数组和哈希表相比，有序数组在等值查问和区间查问场景中的性能十分优良。因为数组为有序的，因而在区间查问的时候，定位起始值和开端值即可，效率十分高。等值查问和哈希表相似，通过 key 值找到对应的 value 值。

但若应用有序数组作为索引数据结构，如果要往有序数组中插入某条记录，则须要移动该记录前面的所有记录，老本较高。

因而，有序数组索引只实用于动态存储引擎，比方你要保留的是 2017 年某个城市的所有人口信息，这类不会再批改的数据。

均衡二叉树

均衡二叉树是比拟常见也是罕用的数据结构，他们的特点如下：

• 均衡二叉树又被称为 AVL 树
• 均衡二叉树是一颗空树或者它的左右两个子树的高度差的绝对值不超过 1，并且左右子树也是均衡树
• 非叶子节点值大于左子节点值而小于右子节点值
• 非叶子节点最多领有两个子节点

应用均衡二叉树作为索引数据结构，有几点不足之处：

思考到极其状况下，每次插入的数据都比上一次插入的数据大，那么用均衡二叉树就会以线性形式进行存储，工夫复杂度为 O(n)。数据量很大时，在 mysql 中一张表存储百万条数据是很失常的一件事，这样会导致树的深度更深，mysql 读取时耗费大量 io。

mysql 进行过磁盘读取时，是以页为单位进行读取，每个节点示意一页。而均衡二叉树每个节点存储一个关键词，导致存储空间被节约。

InnoDB 索引模型

在 InnoDB 中，表都是依据主键程序以索引的模式寄存的，这种存储形式的表称为索引组织表。InnoDB 引擎默认应用 B + 树作为索引数据结构，所有的数据都存储在 B + 树中的。

每一个索引在 InnoDB 外面对应一棵 B+ 树。

B+ 树特点

• 非叶子节点中不存储 data，只存储索引，能够放更多的索引
• 叶子节点蕴含所有索引字段
• 叶子节点蕴含数据 (key 和 data 域) 和指针
• 叶子节点用指针连贯，进步区间拜访的性能

图片:

主键索引和一般索引

在 InnoDB 引擎中，索引类型能够分为主键索引和一般索引。

假如，咱们有一个主键列为 ID 的表，表中有字段 k，并且在 k 上有索引。

这个表的建表语句是：

mysql> create table T(
id int primary key, 
k int not null, 
name varchar(16),
index (k))engine=InnoDB;

表中 R1~R5 的 (ID,k) 值别离为 (100,1)、(200,2)、(300,3)、(500,5) 和(600,6)，两棵树的示例示意图如下

从图中不难看出，依据叶子节点的内容，索引类型分为主键索引和非主键索引。

主键索引的叶子节点存的是整行数据。在 InnoDB 里，主键索引也被称为聚簇索引（clustered index）。

非主键索引的叶子节点内容是主键的值。在 InnoDB 里，非主键索引也被称为二级索引（secondary index）。

依据下面的索引构造阐明，咱们来探讨一个问题：基于主键索引和一般索引的查问有什么区别？
如果语句是 select * from T where ID=500，即主键查问形式，则只须要搜寻 ID 这棵 B+ 树；
如果语句是 select * from T where k=5，即一般索引查问形式，则须要先搜寻 k 索引树，失去 ID 的值为 500，再到 ID 索引树搜寻一次。这个过程称为回表。也就是说，基于非主键索引的查问须要多扫描一棵索引树。因而，咱们在利用中应该尽量应用主键查问。

页决裂和页合并

B+ 树为了保护索引的有序性，在插入新值的时候会做必要的保护。以上图为例，当初要插入一个 ID 值为 700 的记录，则只须要在 ID 为 600 的记录前面新增即可。但如果新增一条 ID 值为 400 的记录，就绝对麻烦了，须要逻辑上移动前面的数据，空出地位。

而更糟的状况是，如果 R5 所在的数据页曾经满了，依据 B+ 树的算法，这时候须要申请一个新的数据页，而后移动局部数据过来。这个过程称为页决裂。在这种状况下，性能天然会受影响。

除了性能外，页决裂操作还影响数据页的利用率。本来放在一个页的数据，当初分到两个页中，整体空间利用率升高大概 50%。

当然有决裂就有合并。当相邻两个页因为删除了数据，利用率很低之后，会将数据页做合并。合并的过程，能够认为是决裂过程的逆过程。

主键为什么倡议抉择自增主键？

如果选用自增主键的话，每次新增数据时，都是以追加的模式进行存储的，这样就不会波及移动数据操作，也不会呈现上述所说的页决裂问题。

如果说采纳业务字段作为主键的话，每次新增数据时，都会进行索引保护，放弃索引的有序性，造成写数据老本较高。

除了性能方面有区别外，再来看看存储方面。假如你的表中的确有一个惟一字段，比方字符串类型的身份证号，那应该用身份证号做主键，还是用自增字段做主键呢？

表中如果应用自增主键的话，若应用 bigint 做主键，占 8 个字节；如果应用身份证号作为主键的话，占用 20 字节。

所以，主键长度越小，一般索引的叶子节点就越小，一般索引占用的空间也就越小，页存储索引越多。

上述从性能和存储空间进行剖析采纳自增主键和采纳业务字段作为主键的优缺点，也推断出采纳自增主键是比拟正当的计划。

文章也会继续更新，能够微信搜寻「迈莫 coding」第一工夫浏览。每天分享优质文章、大厂教训、大厂面经，助力面试，是每个程序员值得关注的平台。