欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据库索引

程序员文章站 2024-01-20 21:01:28
...

数据库索引

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

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

索引常见的模型

哈希表

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

数据库索引

搜索指定 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)),需要保持这棵树是平衡二叉树。

数据库索引

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

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

B 树

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

数据库索引

B+ 树

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

数据库索引

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 (上确界)记录比该页中任何主键值都要大的值,这个伪记录分别构成了页中记录的边界。

数据库索引

索引维护

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

数据库索引

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

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

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

程序员开发者社区

数据库索引

相关标签: 数据库SQL