【MySQL数据库】| 索引以及背后的数据结构

🎗️ 主页：小夜时雨
🎗️ 专栏：MySQL数据库
🎗️ 如何优雅的活着，是我找寻的方向

1. 基本知识

1. 概念

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

索引存在的意义就是就是为了加快查询速度！！！（因为实际开发中，查询场景用的多）。
但是也付出了一定的代价：

1. 需要付出额外的空间来保存索引的数据。
2. 索引可能会拖慢新增，删除和修改的速度。

2. 作用

• 数据库中的表，数据，索引之间的关系，类似于书架上的图书，书籍内容和目录的关系。
• 索引所起的作用类似于数据目录，可以快速定位，检索数据。
• 索引对于提高数据库的性能有很大的帮助。

3. 使用场景

要考虑对数据库表的某列或者几列创建索引，需要考虑以下几点：

• 数据量较大，且经常要对这些列进行条件查询
• 插入和修改操作较少
• 索引会占用额外的磁盘空间

那么也就引申出什么时候不要用索引？

1. 经常增删改的列不要建立索引
2. 有大量重复的列不建立索引

2. 索引背后的数据结构

索引背后使用的是 B+ 树。

1. 为什么不使用 二叉搜索树或者哈希表来存储索引数据？

• 对于二叉搜索树：二叉搜索树的特点是，每个非叶子节点都有两个孩子节点，
  如果元素的个数多了，那么树的高度就会很高，自根节点向下搜索需要访问的叶子结点也会非常多，这就大大降低了查询的效率。树的高度相当于是比较次数，对于数据库来说就是 IO 的访问次数。

• 对于哈希表: 虽然查询的快，但是哈希表是 key-value 结构的，需要知道 key 是多少，通过哈希函数来计算到下标，进而查找到数据，但是模糊查询的时候，key 值无法确定，也就查询不到数据了，即是不支持范围查询和模糊查询。

2. 索引结构为什么不使用 B 树(或者B- 树) ？

B 树可以认为是一个N叉搜索树 ，结构如下：

B 树的特点：

每个节点都可以存储多个数据，这些多个数据就划分出了一定的区间，在搜索的时候就不用访问那么多的叶子节点，而是直接在细分的区间去查找，提高了效率。

MySQL索引结构–B+ 树

结构如下：

B+树的特点：

1. 一个节点可以存储 N 个key，N 个key又划分出 N 个区间 （不是 N+1 个区间，看图可知）
2. 整个树的数据都是在 叶子节点上的，所有非叶子节点上的数据都会在叶子节点中出现（同时也是叶子结点的最大值）。也就是每个节点中的 key 值，都会在子结点中出现，同时该key也是子节点的最大值。
3. B+ 树的叶子节点是首尾相连的，类似于链表结构的。
4. 由于叶子节点保存完整的数据，只在叶子节点这里存储每一行的数据，而非叶子节点只保存key值即可

B+ 树的优势：

• 一个节点中保存更多的key值，所以最终树的高度是相对矮的，也就是查询的时候减少了 IO 的访问次数。（这里 IO 特值硬盘的访问）
• 所有的查询都会落在叶子节点，也就是查询任何一个数据，访问 IO 的次数是一样的，也就意味着查询更加稳定（稳定可以对执行效率有一个判断）。
• B+ 树的叶子节点类似于链表结构，方便进行范围查询。
• 由于所有数据都是在叶子节点上，非叶子节点只存储key值，所以非叶子节点占用的空间是比较小的，这些叶子节点可能就是在内存中缓存，有进一步减少了 IO 的访问次数。

总结

• B+树对于哈希表来说，可以处理模糊匹配的场景；
• B+树对于二叉搜索树来说，深度更低，查找效率更高；
• B+树对于B树来说，
  • B树只适合随机检索，而B+树同时支持随机检索和顺序检索；
  • 单一节点可以储存更多的数据，降低查询的IO次数；
  • 所有的查询都需要查找到叶子结点，使得查询性能更稳定；
  • 兄弟节点之间相连形成有序链表，便于范围内查找，增删效率也更高；

🎗️🎗️🎗️ 好啦，到这里有关 数据库索引 的分享就没了，如果感觉做的还不错的话可以点个赞，关注一下，你的支持就是我继续下去的动力，蟹蟹大家了，我们下期再见，拜了个拜~ ☆*: .｡. o(≧▽≦)o .｡.:*☆