索引数据结构千千万，为什么B+Tree独领风骚

男娘i 2023-09-23 16:13 112阅读 0赞

# 索引的由来 #

*  大数据时代谁掌握了数据就是掌握了流量，就是掌握的号召力。面对浩瀚的数据如何存储并非难事， 难点在于如何在大数据面前查询依旧快如闪电！
 *  这时候索引就产生了，索引的产生主要还是借鉴于图书管理员书签的功能。在大数据面前 `es` 产生了，而我们今天要说的索引却不是它 而是目前中小项目中广泛使用的 `mysql` 数据库中的索引。
 *  本文主题着重介绍索引是什么？索引如何存储？为什么这么设计索引？常见的索引有哪些？最后我们在通过案列来分析如何命中索引以及索引失效的部分场景。

# 什么是索引 #

> 索引是创建在表上的，对数据库表中一列或多列的值进行排序的一种结构，可以提高查询的速度。

*  索引是一种[数据结构][Link 1],以协助快速查询,更新数据库中的数据 。 `mysql` 的索引主要由 `B+Tree` 进行存储。在存储主题上又分为聚簇索引和非聚簇索引。

## 聚簇索引 ##

*  聚簇索引从字面上理解就是聚集在一起。所以凡事索引和数据存放在一起的我们就叫做聚簇索引。在`mysql` 中 `INNODB` 的主键索引就是采用的聚簇索引，因为在叶子节点负责存放数据，而非叶子节点负责存放索引。而除了主键索引外其他索引则是非聚簇索引，因为其他索引的叶子节点存储的是主键索引的地址指向。

## 非聚簇索引 ##

*  在 `MyISAM` 引擎中就是非聚簇索引，我们通过它的文件结构也能够看出索引和数据是分开存放的。 非聚簇索引也会带来一些问题。诸如回表
 *  在 `INNODB` 中非主键索引就是非聚簇索引，同时这种非主键索引也会带来一个问题就是二次索引也称回表。因为我们通过非主键索引是无法定位到最终数据的。大部分情况下我们是需要在根据主键索引进行第二次查找的。加入你有一个索引idx\_name
    
     *  `select name from t where name=13` 发生一次索引，不会回表查询
     *  `select * from t where name=13` 发生两次索引，会发生回表
 *  上面第一个sql 不会发生回表是因为我门的sql 发生了索引覆盖，意思是idx\_name 这颗树已经覆盖了我们查询的范围。

# 索引存储结构 #

*  先说结论 `mysql` 中索引是通过 `B+ Tree` 进行存储的。但是在 `mysql` 中一开始是采取的 二叉树存储的。关于树形存储结构都是二叉树。那么我们是`mysql` 中不采用二叉树、红黑树呢？下面我们来分析下采用二叉树、红叉树分别会带来哪些问题。

## 二叉树 ##

*  二叉树是根据顺序在根据大小判断其存储的左右节点的。这就导致如果我们是按递增ID作为索引的话，最终就导致二叉树变成一颗偏向一边的树，换个角度看其实就是链表。

![format_png][]

*  而针对一张表我们往往就是ID作为索引的居多。而ID采用自增策略的居多，所以如果索引采用的是二叉树的，毋庸置疑销量基本无提升，这也是为什么官方放弃 `二叉树` 作为索引存储的数据结构。
 *  而二叉树一共有如下几种极端情况

![format_png 1][]

## 平衡二叉树 ##

*  在开始红黑树之前，我们需要先了解下有种临界状态叫平衡二叉树。
 *  平衡二叉树又叫做Self-balancing binary search tree 。 平衡二叉树是二叉树的一种特例
 *  在二叉树中有一个定义平衡度(平衡因子)的概念。他的公式是左右高度的绝对值。
 *  当这个平衡度<=1的时候我们就称之为平衡二叉树
 *  在平衡二叉树中他的高度是最稳定的，换句话说平衡二叉树和其他二叉树相比能够在相同的节点情况下保证树的高度最低；这也是为什么mysql中索引的结构是一种平衡二叉树的升级版

![format_png 2][]

## 红黑树 ##

> 红黑树实际上是一颗平衡二叉树；所以在构建的过程中他会发生自平衡

![format_png 3][]

*  因为二叉树在极端的情况会变成一个链表，针对链表的问题红黑树的自平衡特性就完美的规避了二叉树的缺点。那么为什么最终索引也不是选择红黑树呢？
 *  仔细观察能够发现红黑树是一颗标准的二叉树。他所能容纳的最大节点数和他的高度正好成二的次方这个关系。也就是说假设红黑树的高度是h ，那么他能容纳最多的节点为 2^h。
 *  这样看来在数据量过大时，通过红黑树去构建貌似这颗二叉树高度就过去庞大了。高度也高给我们查询就带来更多次交互。要知道每个节点都是存储在硬盘中的，那么每一次的访问都会带来一次IO消耗。所以为了能够提高查询效率 `mysql` 最终还是没有选择红黑树。

①、每个节点要么红色要么黑色

②、根节点是黑色的

③、叶子节点是黑色的

④、红色节点的子节点一定是黑色的

⑤、从一个节点出发，到达任意一个叶子结点(NULL)路径上一定具有相同的黑色节点（保证了平衡度<=2）

![format_png 4][]

## BTree ##

> BTree的设计主要是针对磁盘获取其他存储的一种平衡树(不一定是二叉这里往往指的是多叉)

![format_png 5][]

*  B树非常适合读取和写入相对较大的数据块（如光盘）的存储系统。它通常用于数据库和文件系统。
 *  总结下BTree 具有如下特点：

①、至少是2阶，即至少有两个子节点 ②、对于m阶BTree来说，非根节点所包含的关键词个数j需要满足 (m/2)-1<=j<=m-1 ③、除叶子结点外，节点内关键词个数+1总是等于指针个数 ④、所有叶子结点都在同一层 ⑤、每个关键字保存实际磁盘数据

## B+Tree ##

> B+Tree 是BTree的一种变体。BTree节点里出了索引还会存储指针数据，而B+Tree仅存储索引值，这样同样空间节点能够存储更多的索引

*  B+Tree 因为压缩了数据存储空间，这样就能够在相同高度的BTree上存储更多的索引，这样更加提高索引定位销率。

![format_png 6][]

## Hash表 ##

①、hash索引无法进行范围查询，因为上述的hash结构是没有顺序的，hash索引只能实现等于、In等查询 ②、hash值是针对元数据的一种散列运算。hash值得大小并不能反应元数据的大小。元数据a 、b对应的hash值有可能是3333、2222,而实际上上a<b . 所以我们无法通过hash值进行排序，从而hash索引无法进行排序 ③、对于组合索引来说，在B+Tree中我们有最左匹配原则，但是在hash索引中是不支持的。因为组合索引整个映射成hash值，我们通过联合索引中部分值进行hash运算得带的值与hash索引中是没有关系的 ④、hash索引在查询时是需要遍历整个hash表的。这点我们Java中的HashMap一样 ⑤、hash索引在数据量少的情况下比BTree快。但是当hash冲突比较多的时候定位就会比B+Tree慢很多了。

![format_png 7][]

# 总结 #

*  现在看来数据库运行的很牛逼，而且索引也很快，但这并不是一口吃成胖子的，了解了索引的底层数据结构后我们也能够了解 `mysql` 也是一步一步尝试过来的， 索引也是不断的优化而成的。说不定以后还会有其他结构产生，只能说每种数据结构都是最好的，前提是在特定的场景下。

[Link 1]: https://link.juejin.cn?target=
[format_png]: https://img-blog.csdnimg.cn/img_convert/bd73b9d34dbfbfbcaf6fc0f7e5b726a3.webp?x-oss-process=image/format,png
[format_png 1]: https://img-blog.csdnimg.cn/img_convert/9b617e557bd26626e11bd5e14dfa94c9.webp?x-oss-process=image/format,png
[format_png 2]: https://img-blog.csdnimg.cn/img_convert/c68080cb36b6a66ca1e9d0cb3cb2d739.webp?x-oss-process=image/format,png
[format_png 3]: https://img-blog.csdnimg.cn/img_convert/da53a9a885c7643f6c9b95d8b914c496.webp?x-oss-process=image/format,png
[format_png 4]: https://img-blog.csdnimg.cn/img_convert/8eea82649768b485dee07c359e11681c.webp?x-oss-process=image/format,png
[format_png 5]: https://img-blog.csdnimg.cn/img_convert/7de51dfd91ab7e2a187ee8e2c497daac.webp?x-oss-process=image/format,png
[format_png 6]: https://img-blog.csdnimg.cn/img_convert/ac347bde42aaf02e2f453a80de9a2d2e.webp?x-oss-process=image/format,png
[format_png 7]: https://img-blog.csdnimg.cn/img_convert/b208f186ae202fbd36d08c93bbad98c8.webp?x-oss-process=image/format,png