一看就懂的"什么是XXX"系列--什么是索引

提到“索引”这个概念，读者大致都能说出“提升查询速度”，但若是更进一步的问“如何实现提升查询速度？底层原理是什么？”，读者也许就止步于此了。那么本篇文章就带领读者探寻一下索引是如何做到快速查询的。

#温馨提示：本篇的逻辑性较强，需要读者耐心阅读，仔细琢磨

读者的收获

1、了解索引的概念

2、索引的作用

3、索引的底层结构

4、索引的查询逻辑

5、索引的种类

什么是索引

索引（index）是能够帮助数据库提升数据查询效率的一种数据结构。换一种易懂的说法：索引是一种数据结构，它的作用是使数据库查询数据更快。

数据库对于索引的处理过程

在我们为表的某个字段设置索引之后，数据库会将该字段数据复制，并将复制的数据以某种数据结构重新排列，保存为索引文件。

当使用索引字段做查询条件对该表进行查询操作的时候，数据库会先打开索引文件并通过其中的数据结构来快速定位目标数据。

索引应用的数据结构

既然已经了解到索引是一种数据结构，那么接下来的讲解重点就是研究数据结构了。

鉴于本篇讨论的核心是索引，所以侧重点不在科普各种数据结构，这里只介绍索引使用的数据结构：B TREE（Balance tree）、B+TREE

B TREE和B+TREE是一种优化关系：B TREE先出现，通过对B TREE的优化设计产生了B+TREE。所以首先介绍B TREE：

B TREE（平衡树）

上图为一个B TREE的结构示例，下面对B TREE中的元素逐一说明，读者需要结合图片理解：

1、阶：阶表示B TREE的层数（横向），那么该B TREE为3阶平衡树

2、节点：每个灰色方形叫做一个节点，位于最顶部的叫做根节点，最底部是叶子节点，剩下的则是中间节点。每个节点中包含下列元素：

K : 关键字（存放索引字段）

D : 关键字对应详细数据Data

P：指针（pointer），指向下方子节点

B TREE的特点：

1、叶子节点无p指针

2、指针p和关键字K交叉排列，所以每个节点中的指针P一定比关键字K多一个

3、关键字从左到右有序排列（K后的序号顺序）

4、所有子节点的关键字范围不得超过指针对应父节点左右两侧关键字的范围。

5、所有叶子节点的深度（阶数）相同

6、所有节点的关键字不重复（关键字可能不必走到叶子节点即可命中Data）

通过B TREE的结构可以分析出：B TREE以类似二分的结构，通过范围过滤的算法来提高查询效率，当关键字K在某节点命中后，获取该K的data来返回查询结果，这就是索引的底层原理。

B +TREE

B+TREE是基于B TREE 的一种增强设计，如果读者理解了B TREE，那么B+TREE就简单的多：

B TREE的特点：

1、节点中关键字x与指针p个数相同

2、目标数据只有到达叶子节点才会命中（data数据只存在于叶子节点），也就是说使用B+TREE的索引一定会走到叶子节点

3、每个叶子节点增加一个指针，按顺序指向相邻叶子节点（提升区间访问性能）

以上就是索引采用的两种底层数据结构，目前数据库产品的索引大都基于这两种数据结构，接下来以MYSQL为例看一下索引的应用实例：

MYSQL索引实现

首先读者需要清楚的是：mysql中的索引是采用B+TREE实现的。另外，在mysql中有一个存储引擎的概念（可以理解为mysql存数据的一个中间处理器）。

之所以提及这个概念是因为不同存储引擎下对B+TREE的实现逻辑有所不同，本篇针对常用的两种存储引擎MyISAM、InnoDB中B+TREE的实现逻辑做说明：

MyISAM

在MyISAM存储引擎中索引的实现逻辑是：在B+TREE的叶子节点中存放着对应记录的内存地址D，然后再通过该地址D关联对应表数据以获取详细数据，这种设计方式实现的索引叫做“非聚合索引”。

InnoDB

与MyISAM最核心的区别是：在InnoDB存储引擎中，叶子节点直接存放了数据详细信息，也就是说InnoDB直接将表数据本身做成了B+TREE数据结构（由于不需要再查一次表数据，这使得查询速度更快），这种设计方式实现的索引叫做“聚合索引”。

以上就是索引的底层逻辑，其实学习的核心就在于知识的底层逻辑，当你了解了底层逻辑之后，有些问题是不需要刻意去记的。

本篇涉及数据结构和算法，逻辑性较强，所以读者想要完全理解可能需要反复阅读几次。浩说编程致力于为读者解惑，关注我，你会学到更多。