目录
什么是索引
索引的作用
索引的使用
查询索引
创建索引
删除索引
索引底层数据结构实现
什么是索引
索引(index)是用于提高查询性能的数据结构。可以大大加快数据检索速度,但会增加写入和存储的开销
索引的作用
索引的作用类似于一本书的目录
当需要找到找到书中某个章节的所在位置时,就可以查找目录,方便我们快速定位
因此,索引的特点:
(1)加快查询速度
(2)索引需要存储一定的索引结构,因此会存在额外的存储开销
(3)当我们需要进行 新增、删除 和 修改 的时候,也需要针对索引进行更新。对索引进行更新,也是额外的开销
因此,当我们需要根据条件进行查找时,索引就能帮助我们检索数据、快速定位,提升性能
但当我们需要进行 新增、删除 和 修改 时,就需要修改(维护)索引,此时就会降低性能
因此,在适用索引之前需要考虑以下几点:
(1)数据量比较大,且需要经常对这些列进行条件查询
(2)该数据库表的插入、更新 和 修改 操作的频率低
(3)索引会占用额外的磁盘空间
若满足以上条件,则可以考虑对表中字段创建索引,以提高效率
反之,若非条件查询列,或经常执行 插入、修改 和 删除 操作,或磁盘空间不足,则不考虑创建索引
索引的使用
查询索引
show index from table;
例如:
我们创建一张学生表:
drop table if exists student;
create table student (
id int primary key,
name varchar(10) unique,
chinese int,
math int,
english int
);
查看索引:
show index from student;
‘
当创建 主键约束(primary key)、唯一约束(unique)和 外键约束(foreign key)时,会自动创建对应列的索引
一个表的索引可以有多个,每个索引都是根据某个具体的列来展开的,后续按照这个列来进行查询时才能提高效率
就像字典,包含了多个目录,可以根据拼音、部首、笔画...等不同目录来进行检索
创建索引
对于非主键、非唯一约束、非外键的字段,可以创建普通索引
create index 索引名 on table_name(列名);
为 chinese 字段创建普通索引:
create index index_student_chinese on student(chinese);
创建成功:
由于此时数据表为空(或在数据比较少的情况下),此时创建索引就没有任何问题,但是如果表本身就有很多数据,此时创建索引操作就会触发大量硬盘IO,数据库就可能会挂掉
删除索引
drop index 索引名 on table_name;
删除 chinese 的索引:
drop index index_student_chinese on student;
与添加索引一样,删除索引也是一个危险操作
因此,当我们需要创建索引时,一定要在建表时就规划好
索引底层数据结构实现
索引其实是通过额外的数据结构,来针对表中的数据进行重新组织,不同的数据结构适用于不同类型的查询和场景
那么,索引是怎样来对数据进行重新组织呢?
一般使用 B+ 树来实现索引,在了解 B+ 树之前,我们先来了解 B 树
B 树(B-树 B-Tree):B 树是一种自平衡的树数据结构,可以保持数据的有序性并允许以对数时间复杂度进行搜索、插入和删除操作
我们通过一个具体的例子来进一步理解:
B树是一颗N叉搜索树,一个节点上包含N个key,按照顺序排列,N个值划分出了 N + 1 个区间:
由于是N叉树,相比于二叉树,同样的高度,能表示的元素就会多很多,这样当我们使用B树进行查询时,比较的次数就会比二叉搜索树少很多
且由于节点内的值是有序的,就能够在节点内部进行二分查找,从而加速搜索过程
更重要的是,同一个节点中的key都是一次硬盘IO读取出来的,即使同一个节点上的比较次数增加了,但是硬盘IO的次数少了(一次硬盘IO 大概相当于 内存 中的1万次比较)
接着,我们来看B+树
B+树(B+ Tree):B+树是B-树的一种变体,在B树的基础上做出了改进,其所有的值都存储在叶子节点中,而非叶子节点只存储键值,用于引导搜索
B+ 树也是一颗N叉搜索树,每个节点包含多个key,N 个 key 划分出 N 个区间:
其中,每个节点的 N 个 key 中,都会存在一个最大值(或最小值)
每个节点中的 key,都会在子树重复出现,这样重复出现,带来的好处是所有数据都包含在叶子节点这一层中
叶子节点之间使用链式结构相连
所有的数据出现在叶子节点中,当查询任何一个元素时,都需要从根节点查询到叶子节点,过程中经过的硬盘IO次数是一样的,因此,使用 B+ 树查询的时间是稳定的
将叶子节点连接起来,在进行范围查询时,就会快很多
例如:
进行查询范围:between 15 and 50 之间的数据:
此时,只需要查找到最开头的数据,再沿着链表向后遍历,即可找到所有满足条件的数据: