谈谈对数据库索引的认识

╰+哭是因爲堅強的太久メ 2024-05-06 21:26 82阅读 0赞

## 索引的概念 ##

索引是一种特殊的文件，包含着对数据表里所有记录的引用指针。  
可以对表中的一列或多列创建索引，并指定索引的类型，各类索引有各自的数据结构实现。

## 索引的作用 ##

默认情况下，进行条件查询操作，就是遍历表，一条一条数据都带入条件。  
引入索引，就是要通过引入其他的数据结构(比如B+树)，来加快查询的速度，减少遍历表的可能性

## 索引的使用场景 ##

对某数据库表的某列或某几列创建索引时，考虑的因素：

1.  数据量较大，且经常对这些列进行条件查询
2.  该数据库表的插入操作，及对这些列的修改操作频率较低
3.  磁盘空间足够，因为创建的索引会占用额外的磁盘空间

当满足以上条件时，可以对表中的这些字段创建索引，以提高查询效率。  
反之，如果非条件查询列，或经常做插入、修改操作，或磁盘空间不足时，不考虑创建索引。

## 索引背后的数据结构 ##

### 原有的用来查询的数据结构: **二叉搜索树(红黑树)，哈希表** ###

**哈希表**：只能查询key相等的情况，无法进行`<`(小于)，`>`（大于)这样的范围查询.  
原因：经过 hash 函数的映射,原来 key 之间的大小关系,不能反应到计算出来的 hash 值的大小关系,也无法决定下标的大小关系  
结论：哈系表不适合作为数据库查询的数据结构  
  
  
**红黑树**：  
（1）红黑树里面的元素是有序的,可以进行范围查询了,但是它在查找某些节点的效率不高  
原因：  
如下图所示：找左树最右节点的后继 => 即找节点22的后继：节点25  
需要往父节点上一系列回溯，才能找到它  
注：找右数最左节点的前驱也是一样的  
此处可以通过"线索化"的方式来解决，但是要付出更多的存储空间，也是不合适的  
![在这里插入图片描述][842e63b5cda34263bca1003334f5b2e5.png]

（2）红黑树是二叉搜索树，当元素非常多的时候,就会使树的高度,变的比较高,树的高度越高,进行查询的效率就越低.  
原因：  
a) 高度每增加一层,比较次数就增加1  
b) 数据库的数据/索引都是保存在硬盘上的.上述的每次比较，就都需要一次硬盘IO操作了  
结论：红黑树不太适合于大规模在硬盘上管理数据的场景

### B+ 树的前身：B 树的诞生 ###

B树，本质上是一个N叉搜索树．  
每个节点上可以存储多个元素，延伸出多个子树.  
表示同样数量的数据，需要的节点数就少了，对应的树的高度也大大降低了.

B树结构模型如下图：  
![在这里插入图片描述][4bde950267234040926c907397cf940e.png]

B 树的优势：

1.  每个节点上的这些 key 是有序排列的，比较的时候可以直接二分查找.
2.  B树也会保证让其节点上保存的 key 不会太多，如果插入更多的元素,使 key 变多了，改节点分裂出更多的子树出来
3.  多个数据，都是放在一块连续的存储空间上，进行比较的时候，一次硬盘IO就能读出整个节点，就可以直接完成上述比较 (进行多次比较,实际上只有一次硬盘IO

注：B 树 也被称为 B- 树

### 索引数据结构的最终形态：六边形战士 B+ 树 正式登场 ###

B+ 树 是 B 树的升级版，同样的，B+ 树也是 N 叉搜索树

B+ 树结构模型如下图：  
![在这里插入图片描述][4f055ec9fdb8475d8e2e16ac058a48d7.png]  
1）按照上述规则来排列数据, 此时叶子节点这一层,就包含了整个数据集合的全集  
2）另外, B＋树,会把叶子结点通过类似于链表这样的链式结构串起来。此时就可以通过上述链式结构非常方便的遍历整个表中的所有数据,同时也非常方便进行范围查询。比如，查询 id >= 5 and id < 9 此时进行的范围查询就非常简单高效

B+ 树相比于 B 树的优势：

1.  非常方便进行遍历和范围查询
2.  当前任何一次查询操作，最终都是要落到叶子节点完成的，所以，查询任何数据,经历的硬盘IO的次数都是一样的。这个时候,查询操作消耗的时间是**稳定的**；如果是B树的结构, 有的元素,直接在非叶子节点就查到了，IO次数更少,就会出现有些 key 查的快,有些 key 查的不快(IO次数有很大影响) **不稳定**
3.  由于叶子节点，是数据的全集，对应的非叶子节点中，都是重复出现的数据。就可以把表每一行的数据，最终都关联到叶子节点这一层.非叶子节点中只保存一个单纯的 key 值即可  
    例子：`student(id, name, classId, gender, score)`  
    此时，比如使用`id`这一列来做索引.这里B+树的非叶子节点,都只需要保存一个`id`这样的值就行了.到了叶子节点这里,每个叶子节点不光要保存 `id`,还要把后续的`name`, `classld`等信息也保存起来.

--------------------

> 我们看到数据库的"表格"只是一个逻辑上的结构实际上底层的结构,就是这个B+树的结构，就会按照主键的索引的这个B+树的叶子节点来保存每一行的数据。  
> 如果你的表,创建主键了，自然是通过你创建的主键的索引的B+树来组织所有行；如果你没创建主键, mysql其实生成了一个隐藏的主键,按照隐藏主键构造的树来组织。  
> 这样组织之后,非叶子节点占用的空间就比较小(非叶子节点只存id)此时,非叶子节点就可以缓存到内存中（这份数据必然要在硬盘上也保存一份,为了提高查询速度,就可以把这部分结构放到内存中了)这样查询速度又大大提高了(非叶子节点中的比较不再收到硬盘IO的制约了)

注：B＋树存在的前提,使用了innodb这个存储引擎，mysql支持多种存储引擎，不同的存储引擎使用的索引的数据结构是不同的.

> 针对哪个列创建索引,就是针对哪个列构建B＋树.  
> 主键索引的B+树,叶子节点是带有数据行的.其他的列的索引,叶子节点,则是主键id  
> 针对非主键列进行索引查询,查到的结果是一个主键id，还需要去主键索引中再做一次查询(称为"回表")

> 针对索引列进行查询,就是从树根节点往下一层一层的查询  
> 针对非索引列查询,就拿着最底下一层叶子节点,遍历链表就行了.

--------------------

## 索引的使用 ##

*  **查看索引**

show index from 表名;

示例：查看班级表已有的数据

show index from class;

*  **创建索引**  
    对于非主键、非唯一约束、非外键的字段，可以创建普通索引

create index 索引名 on 表名(字段名);

示例：创建学生表中学生ID的索引

create index index_student_id on student(student_id);

*  **删除索引**

drop index 索引名 on 表名;

示例：删除学生表中学生ID的索引

drop index student_id on student;

[842e63b5cda34263bca1003334f5b2e5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/86b8886363654f55b3b9f01c13ec7d4a.png
[4bde950267234040926c907397cf940e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/bbb5895d87e44dab9464cfb170fb0593.png
[4f055ec9fdb8475d8e2e16ac058a48d7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/91469bc489e34427b0b4d8f66060ad9a.png