资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

数据库索引的数据结构和原理介绍

创作时间:

作者:

@小白创作中心

数据库索引的数据结构和原理介绍

引用

CSDN

https://blog.csdn.net/zxd1435513775/article/details/86489764

索引是数据库中非常重要的一种数据结构，它能够显著提高数据查询的效率。本文将详细介绍数据库索引的基本概念、类型、优缺点以及其底层的存储结构，特别是B+树的原理和应用。

一、引言

当我们新建一个没有主键的表时，插入的数据会以无序的方式存储在磁盘上，仅与插入顺序相关。在这种情况下，查询数据需要逐一比较每条记录，效率极低。因此，建立索引成为提高查询效率的关键手段。那么，什么是索引？为什么建立索引能提高查询效率？接下来将详细探讨这些问题。

二、索引

何为索引？

在关系型数据库中，索引是一种单独的、物理的存储结构，用于对数据库表中一列或多列的值进行排序。它包含了索引列的值和指向具体记录的逻辑指针。索引提供指向存储在表的指定列中的数据值的指针，并根据指定的排序顺序对这些指针进行排序。数据库使用索引可以快速定位特定值，并通过指针找到包含该值的行，从而加速SQL语句的执行。

索引类型

根据数据库的功能，可以在数据库设计器中创建四种索引：普通索引、唯一索引、主键索引和聚集索引。

普通索引：最基本的索引类型，没有唯一性限制。可以通过以下方式创建：

create index <索引的名字> on tablename (列的列表);
alter table tablename add index [索引的名字] (列的列表);
create table tablename ( [...], index [索引的名字] (列的列表) );

唯一索引（UNIQUE）：不允许其中任何两行具有相同索引值的索引。当现有数据中存在重复的键值时，大多数数据库不允许将新创建的唯一索引与表一起保存。创建唯一索引的方式如下：
```
create unique index <索引的名字> on tablename (列的列表);
alter table tablename add unique [索引的名字] (列的列表);
create table tablename ( [...], unique [索引的名字] (列的列表) );
```
主键索引：数据库表中一列或列组合的值唯一标识表中的每一行。该列称为表的主键。为表定义主键将自动创建主键索引，主键索引是唯一索引的特定类型，要求主键中的每个值都唯一。
聚集索引（CLUSTERED）：在聚集索引中，表中行的物理顺序与键值的逻辑（索引）顺序相同。一个表只能包含一个聚集索引。聚集索引通常提供更快的数据访问速度，但更适合于很少对基表进行增删改操作的情况。

索引的优缺点

优点：
1. 大大加快数据的检索速度
2. 创建唯一性索引，保证数据库表中每一行数据的唯一性
3. 加速表和表之间的连接
4. 在使用分组和排序子句进行数据检索时，可以显著减少查询中分组和排序的时间
缺点：
1. 索引需要占物理空间
2. 当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，降低了数据的维护速度

三、索引的存储结构

在MySQL引擎与锁机制中提到，InnoDB和MyISAM两种引擎所使用的索引的数据结构都是B+树。

索引原理

数据库查询面临着等值查询、范围查询（>、<、between、in）、模糊查询（like）和并集查询（or）等多种场景。为了应对这些查询问题，可以将数据分成段进行分段查询。例如，如果有1000条数据，可以将其分为1到100、101到200等段，这样可以快速定位数据。但对于大规模数据，简单的搜索树难以满足复杂的应用场景。

磁盘IO与预读

磁盘读取数据的时间主要由寻道时间、旋转延迟和传输时间组成。每次磁盘IO的时间约等于9ms左右，而数据库动辄需要处理十万百万乃至千万级数据，因此需要优化磁盘IO操作。操作系统通过预读机制，每次IO时不仅读取当前磁盘地址的数据，还会读取相邻的数据到内存缓冲区，以减少后续的IO操作。

索引的数据结构

为了控制每次查找数据时的磁盘IO次数，B+树应运而生。B+树的每个磁盘块包含几个数据项和指针，真实的数据存在于叶子节点，非叶子节点只存储指引搜索方向的数据项。

详解使用B+树查找数据过程

以一棵B+树为例，浅蓝色的块称之为一个磁盘块，可以看到每个磁盘块包含几个数据项（深蓝色所示）和指针（黄色所示）。如磁盘块1包含数据项17和35，包含指针P1、P2、P3，P1表示小于17的磁盘块，P2表示在17和35之间的磁盘块，P3表示大于35的磁盘块。真实的数据存在于叶子节点即3、5、9、10、13、15、28、29、36、60、75、79、90、99。非叶子节点不存储真实的数据，只存储指引搜索方向的数据项，如17、35并不真实存在于数据表中。

B+树的查找过程

在上图中，如果要查找数据项29，那么首先会把磁盘块1由磁盘加载到内存，此时发生一次IO，在内存中用二分查找确定29在17和35之间，锁定磁盘块1的P2指针，内存时间因为非常短（相比磁盘的IO）可以忽略不计，通过磁盘块1的P2指针的磁盘地址把磁盘块3由磁盘加载到内存，发生第二次IO，29在26和30之间，锁定磁盘块3的P2指针，通过指针加载磁盘块8到内存，发生第三次IO，同时内存中做二分查找找到29，结束查询，总计三次IO。真实的情况是，3层的B+树可以表示上百万的数据，如果上百万的数据查找只需要三次IO，性能提高将是巨大的，如果没有索引，每个数据项都要发生一次IO，那么总共需要百万次的IO，显然成本非常非常高。

B+树性质

性质一：

通过上面的分析，我们知道IO次数取决于B+数的高度 h，假设当前数据表的数据为 N，每个磁盘块的数据项的数量是m，则有h=㏒(m+1)N。当数据量N一定的情况下，m越大，h越小；而m = 磁盘块的大小 / 数据项的大小，磁盘块的大小也就是一个数据页的大小，是固定的，如果数据项占的空间越小，数据项的数量越多，树的高度越低。

结论：这就是为什么每个数据项，即索引字段要尽量的小，比如int占4字节，要比bigint8字节少一半。这也是为什么B+树要求把真实的数据放到叶子节点而不是内层节点，一旦放到内层节点，磁盘块的数据项会大幅度下降，导致树增高。当数据项等于1时将会退化成线性表。

B+树的高度计算：第一层为m个数据项，第二层为(m+1)m个数据项，第三层为(m+1)(m+1)*m个数据项，第四层依次类推，最后用等比公式的求和公式，就可以得到上面的公式。

性质二：

当B+树的数据项是复合的数据结构，比如(name,age,sex)的时候，B+数是按照从左到右的顺序来建立搜索树的，比如当(张三,20,F)这样的数据来检索的时候，B+树会优先比较name来确定下一步的搜索方向，如果name相同再依次比较age和sex，最后得到检索的数据；但当(20,F)这样的没有name的数据来的时候，B+树就不知道下一步该查哪个节点，因为建立搜索树的时候name就是第一个比较因子，必须要先根据name来搜索才能知道下一步去哪里查询（索引失效）。比如当(张三,F)这样的数据来检索时，B+树可以用name来指定搜索方向，但下一个字段age的缺失，所以只能把名字等于张三的数据都找到，然后再匹配性别是F的数据了，这个是非常重要的性质，即索引的最左匹配特性。

注意：索引的最左前缀原则

慢查询优化

了解完索引原理之后，我们来看看慢查询，大家是不是有什么想法呢？先总结一下索引的几大基本原则。

建索引的几大原则

（1）、最左前缀匹配原则。MySQL会一直向右匹配直到遇到范围查询(>、<、between、like)就停止匹配，比如a = 1 and b = 2 and c > 3 and d = 4 如果建立(a,b,c,d)顺序的索引，d是用不到索引的，如果建立(a,b,d,c)的索引则都可以用到，a,b,d的顺序可以任意调整。

（2）、= 和 in 可以乱序。比如a = 1 and b = 2 and c = 3 建立(a,b,c)索引可以任意顺序，MySQL的查询优化器会帮你优化成索引可以识别的形式。

（3）、尽量选择区分度高的列作为索引，区分度的公式是count(distinct col)/count(*)，表示字段不重复的比例。比例越大我们扫描的记录数越少，唯一键的区分度是1，而一些状态、性别字段可能在大数据面前区分度就是0，那可能有人会问，这个比例有什么经验值吗？使用场景不同，这个值也很难确定，一般需要join的字段我们都要求是0.1以上，即平均1条扫描10条记录。

（4）、索引列不能参与计算，保持列“干净”。比如from_unixtime(create_time) = ’2019-01-13’就不能使用到索引，原因很简单，B+树中存的都是数据表中的字段值，但进行检索时，需要把所有元素都应用函数才能比较，显然成本太大。所以语句应该写成create_time = unix_timestamp(’2019-01-13’)。

（5）、尽量的扩展索引，不要新建索引。比如表中已经有a的索引，现在要加(a,b)的索引，那么只需要修改原来的索引即可。