数据库索引

数据库索引

数据库索引,在日常工作中会经常接触到,比如某一个 SQL 查询比较慢,分析原因后,经常会说 “给某个字段加个索引”,索引又是如何工作的?

索引的出现是为了提高数据查询的效率,和书的目录是一样的。

索引常见的模型

哈希表

哈希表示一种 以键值对(key-Value)存储数据的结构,我们只要输入待查找是值 key,就可以找到其对应的值即 Value。哈希的思路很简单,把值放在数组里,用一个哈希函数把 key 换算成一个确定的位置。然后把 value 放在数组的这个位置。有点类似 HashMap 的数据结构,多个key 值经过哈希函数的换算,会出现同一个值的情况,处理这种情况的一种方法是,拉出一个链表。

image

搜索指定 key 值的场景

图中,User2 和 User4 根据身份证号算出的值都是 N,但是没关系,后面有个列表,假设,这个是要查 ID_card_n2 对应的名字是什么,将 ID_card_n2 通过哈希值算出 N; 然后,按照顺序遍历,找到 User2。

搜索指定 key 范围的场景

如果按照索引结构支持范围查询,比如查身份证号在[ID_card_X,ID_card_Y] 区间的 User,可以先用二分法找到 ID_card_X (如果不存在 ID_card_X,就找到大于 ID_card_X 的第一个 User),然后向右遍历,知道查到第一个大于ID_card_Y的身份证号,退出循环。

如果仅仅看查询效率,这种 hash 表,有序数组是最好的数据结构,但是,在需要更新数据的时候,成本很高,需要往中间插入一个记录,就必须挪动后面索引的记录。

有序数组索引只适用于静态存储引擎比如你保存的数据 2019 年某个城市的人口数据,然后不再修改了。

二叉树排序树

二叉树排序树的特点是:每个节点的左儿子小于父节点,父节点又小于右儿子。

如果这样要查 ID_card_n2 的话,按照下图中的顺序就是按照 UserA->UserC->UserF->User2 这个路径查找的 User2, 这个时间复杂度是 O(log(N))。为了维持O(log(N)),需要保持这棵树是平衡二叉树。

image

树可以是二叉树,也可以是多叉树,多叉数是每个阶段多个儿子,儿子从左到右保持递增,但是实际上大多数的数据库存储用的不是二叉树,索引不止存储在内存中,还要写到磁盘上。

你可以想象一下一棵100万节点的平衡二叉树,树高20.一次查询可能需要访问20个数据块。在机械硬盘时代,从磁盘随机读一个数据块需要10ms左右的寻址时间。也就是说,对于一个100万行的表,如果使用二叉树来存储,单独访问一个行可能需要20个10ms的时间,这个查询可真够慢的。

B 树

B 树本质是多路二叉树;叶节点具有相同深度,叶节点的指针为空;所有索引元素不重复;节点中数据索引从左到右依次递增。

image

B+ 树

非叶子节点不存储数据,只存储索引(冗余)和指针,可以放更多的索引,树高度降低;叶子节点包含索引索引字段;叶子节点比 B 树增加了指针连接;叶子节点有双向指针连接(首尾节点可以通过指针连接),提高区间访问的性能,范围查找。

image

InnoDB 的索引模型

在 InnoDB 中,表都是需要根据主键顺序以索引形式存放,这种存储方式的表称为索引组织表,又因为前面我们提到的,InnoDB 使用 B+ 树索引模型,所以数据都是存储在 B+ 树中。

每个索引在 InnoDB 里面对应一颗 B+ 树。

假设,有一个主键列 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),两棵树的示例示意图如下。其中 ID 是主键, 普通索引为 k;

普通索引和主键索引有啥区别?

主键索引的叶子节点存的是整行数据,在 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+树结构,当插入的数据的时候,由于数据只有一份,通过非主键索引获取到主键值,然后再去主键索引的B+树数据结构中找到对应的行数据,节省了内存空间;
  • 如果非主键索引的叶子节点也存储一份数据,如果通过非主键索引插入数据,那么要向主键索引对应的行数据进行同步,那么会带来数据一致性问题。可以通过事务的方式解决,我们都知道使用事务后,就会对性能有所消耗。

为什么InnoDB推荐使用整型的自增主键?

主键长度越小,普通索引的叶子节点就越小,普通索引占用的空间也就越小。

  • 索引的数据类型是整型,一方面整型占有的磁盘空间或内存空间相比字符串更少,另一方面整型比较比字符串比较更快速,字符串比较是先转换为ASCII码,然后再比较的。
  • 最后,B+树本质是多路多叉树,如果主键索引不是自增的,那么后续插入的索引就会引起B+树的其他节点的分裂和重新平衡,影响数据插入的效率,如果是自增主键,只用在尾节点做增加就可以。从性能和存储空间方面考量,自增主键往往是更合理的选择。

Innodb 逻辑存储结构图

从上往下依次为:Tablespace、Segment、Extent、Page 以及 Row。

Page 结构

Page 数据结构,File Header 字段用于记录 Page 的头信息,其中比较重要的是 FIL_PAGE_PREV 和 FIL_PAGE_NEXT 字段,通过这两个字段,我们可以找到该页的上一页和下一页,实际上所有页通过两个字段可以形成一条双向链表。Page Header 字段用于记录 Page 的状态信息。接下来的 Infimum 和 Supremum 是两个伪行记录,Infimum(下确界)记录比该页中任何主键值都要小的值,Supremum (上确界)记录比该页中任何主键值都要大的值,这个伪记录分别构成了页中记录的边界。

image

索引维护

B+ 树为了维护索引有序性,在插入新值的时候需要做必要的维护,以上面这个图为例,如果插入新的行 ID 值为 700,则只需要在 R5 的记录后面插入一个新记录。如果新插入的 ID 值为 400就相对麻烦,需要移动后面的数据,空出位置。

image

什么场景适合用业务字段做主键索引?

  1. 只有一个索引
  2. 该索引必须是唯一索引

如果没有其他索引,所以也就不用考虑其他索引的叶子节点大小的问题。这时候我们就要优先考虑“尽量使用主键査询”原则,直接将这个索引设置为主键可以避免每次查询需要搜索两棵树。

本文分享自微信公众号 - 程序员开发者社区(gh_016ffe40d550),作者:猿星人

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-05-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • MongoDB 索引

    当往一个集合中插入多个文档后,每个文档经过存储殷引擎后,有一个位置信息,通过这个位置信息。就能从存储引擎中读出该文档。在 mmapv1 引擎下,位置信息是【文件...

    王小明_HIT
  • 数据库索引有哪些?

    如果数据量比较少,是否使用索引对结果的影响并不大,比如数据不超过 1000 行,那么可以不建索引。

    王小明_HIT
  • 数据库索引原理

    在下面这个表T中,如果我执行 select* from t where k between3and5,需要执行几次树的搜索操作,会扫描多少行?

    王小明_HIT
  • BAT大厂都会问的MySQL底层数据结构

    左边子节点的数据小于父节点数据,右边子节点的数据大于父节点数据。如果col2是索引,查找索引为89的行元素,那么只需要查找两次,就可以获取到行元素所在的磁盘指针...

    程序员小强
  • 面试小知识:MySQL索引相关

    如果我们要进行模糊查找,查找name 以“张"开头的所有人的ID,即 sql 语句为

    帅地
  • SQL学习笔记之B+树

    任意节点,它的左子树如果不为空,那么左子树上所有节点的值都小于根节点的值; 任意节点,他的右子树如果不为空,那么右子树上的所有节点的值大于根节点的值。

    Jetpropelledsnake21
  • 一文带你深入理解Mysql索引底层数据结构与算法

    首先看一下,在数据库没有加索引的情况下,SQL中的where语句是如何查找目标记录的,首先看到下图的Col2字段,如果我们要查找where col2 = 89的...

    黎明大大
  • Java后端面试学习知识总结——数据库:MySQL

      关系型数据库,是指采用了关系模型来组织数据的数据库,其以行和列的形式存储数据,以便于用户理解,关系型数据库这一系列的行和列被称为表,一组表组成了数据库。用户...

    星如月勿忘初心
  • 数据库优化

    1)应尽量避免在 where 子句中使用!=或<>操作符,否则将引擎放弃使用索引而进行全表扫描。

    ellipse
  • MySQL|索引背后

    01 索引 以MySQL中的索引为例子总结。 数据库查询是数据库的最主要功能之一,实现高效的查询速度一定是MySQL非常关心的事情。 索引(Index)正是帮...

    double

扫码关注云+社区

领取腾讯云代金券