索引的概念、原理(为什么要建立索引)

1-什么是索引?

索引是存储引擎用于快速查找记录的一种数据结构。在MySQL中,也叫作 "键(key)"。

2-索引原理(为什么索引能加快查找效率?)

索引常用两种数据结构实现,接下来我们来分别看下两种不同的索引。

2-1  B-Tree 索引

要了解B-Tree索引,我们肯定得先对B-Tree 一数据结构有一定的了解。


假设一颗m阶的B树,则其具有以下特点:

\bullet 根节点至少有2个节点

\bullet 除根节点外,每个节点存储的key的数量必须满足:m/2<=x<=m-1 (x为节点存储的key的数量)

\bullet 位于第x-1个和x个之间的key存储的值也必须x-1个和x对应key的值之间

那么应用B树之后为什么查找 效率会高很多呢?我们来举个例子说明


假设这是我们user表中的数据,键值即为我们的 id ,现在我们要查找id为28的记录。

建立索引的情况下:

1、读取磁盘块1中的数据(已经在内存中),判断出应该读取p2指向的磁盘块3.

2、读取磁盘块3中的数据,判断出应该读取p2指向的磁盘块8.

3、读取磁盘快8的数据,查找到id为28的记录。


没有建立索引的情况下:

扫描全表,直到查找到id为28 的记录。

对比有无索引的情况,我们就可以很明显的发现,如果我们的表记录数很大,建立索引后只要保持树的深度H,我们就可以在<=H-1次下,查找到我们的记录(根节点常驻内存)。没有建立索引时,则需要进行扫描全表,很耗费系统资源,且效率非常低下。


2-2 B+Tree 索引

为了理解B+Tree 索引,我们还是先来了解下B+Tree这种数据结构。


B+Tree区别B-Tree(B树)的地方在于,B+Tree的非叶子结点只存储导航信息,数据全部存储在叶子结点处并且用链表连接。

B+Tree 树非叶子结点只起导航作用,这样做的好处是内页可以存储更多的key,数据更紧密,可以简单的理解为B+Tree 相对于B-Tree来说可以进一步降低树的深度,降低io的读取次数,提高效率。

由于磁盘顺序读取的效率很高(不需要寻道时间,只需很少的旋转时间),因此对于具有局部性的程序来说,预读可以提高I/O效率。预读的长度一般为页(page)的整倍数。

数据库的设计者也巧妙的利用磁盘的预读,将每个节点设为一个页的大小,这样我们就可以只需要一次io便可以读取整个节点的信息。


现在我们依旧寻找 id 为28的记录:

1、根据磁盘块1判断应该寻找磁盘块3的数据(根节点常驻内存)。

2、读取磁盘块3的数据,判断出应该读取磁盘块8的数据。

3、读取磁盘块8的数据,寻找到id为28的记录,结束。


看到这里大家可能还不能体会到索引的高效性,我们把数据量扩大点来计算下:

InnoDB存储引擎中页的大小为16kb,为了方便计算我们假设表中id占8个字节,其他数据占8个字节,也就是说一个页,我们可以存储16kb/16B=1000  个键值对(方便计算去进制为1000而不是1024),那么一个深度为3的可以存储多少条数据呢?答案是10^3*10^3*10^3=10亿条记录,而当我们要查找其中一条数据的时候我们只需要进行两次IO(根节点常驻内存)。10亿条数据中查找1条数据,只需要进行2次io,这效率至高相对于没有索引进行一条一条记录扫描是可想而知的。

3-常见存储引擎中的索引

     在讲解概念的时候我们就已经知道索引是存储引擎级别的概念,不同存储引擎对索引的实现方式是不同的,InnoDB和MyISAM的索引底层都是使用B+Tree数据结构,但是使用了两种不同的实现方式。

假设这是我们数据库中的一张表,id为我们的主键(比较懒,id应为第二张图图中的key,3,5,9等等 )

我们依旧拿这张图来讲解,在MyISAM中,叶子节点存储的值(图中的data)不是我们的其他字段的值,而是存储记录的地址。

而在InnoDB中data即为我们除索引键外的数据,在我们的表中也就是encode的值。

依旧是在InnoDB存储引擎下,如果我们在encode上建立了索引,则data中存储的仅仅是我们的主键(不是除encode外所有的数据),查找时拿到我们的主键,再根据我们的主键索引去查找对应的记录。了解不同存储引擎下索引如何工作可以帮助我们排查性能问题。

这里又会延伸出二个概念:聚集索引和非聚集索引

聚集(clustered)索引,也叫聚簇索引。

定义:数据行的物理顺序与列值(一般是主键的那一列)的逻辑顺序相同,一个表中只能拥有一个聚集索引。

概念很难理解,我们可以按照我们上面讲的来理解,根据聚集索引查找我们可以直接查找到们的数据(如我们根据id查找),根据非聚集索引查找时要先找到聚集索引,然后根据聚集索引查找记录(如上面我们根据encode查找)。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容