GBase8s 索引入门之原理分析(一)

GBase8s 索引入门之原理分析(一),第1张

GBase8s 索引入门之原理分析(一)

Gbase8s 索引入门之原理分析(一)

1.数据页的存储结构2.页分裂3.主键索引4.B+ 树实现索引的页存储物理结构5.聚簇索引

1.数据页的存储结构

一般在研究索引之前,需要先知道数据在磁盘上的存储结构,存储方式简单的总结为:
在磁盘文件中,数据页(存储数据的数据结构)之间是组成双向链表的,数据页内部的数据行(每一行数据)是组成单向链表的,而且数据行是根据主键从大到小排序的。如下图:

在引出索引之前,如果表中没有创建索引,是如何根据SQL查询语句查出数据的?

查询方式有两种:根据主键字段查询和根据非主键字段查询。

先看第一种根据主键字段查询,这种查询方式比较简单,直接到数据页的页目录中根据主键进行二分法(ps:比较基础的算法)查找。快速找到主键对应的数据在哪个数据页中,然后到对应的数据页中,遍历数据页中的每一行数据,找到主键对应的数据,然后读取数据行。

第二种根据非主键字段查询,这种方式就不能根据主键的页目录进行二分查找了,只能进入每一个数据页中,一行一行的对比,依次遍历查找,也就是全表扫描。(这种方式在遍历所有的数据页时还需要把数据页加载到内存中,再依次对比查找)

众所周知,全表扫描在数据较多的情况下,效率极低,所以就需要通过创建索引来查询。

2.页分裂

在引入索引概念之前,还需要知道一个前提知识,页分裂。

一个数据页写满了,就要换下一页去写,下一个数据页要求主键值是比上一页大的。

主键值是自增id是很容易做到这一点的。但是有些情况下,主键值不是自增id,比如uuid,那么在往下一个数据页写数据的时候,就很可能产生页分裂,把值小的数据行移动到前面的页去,把前面页较大的数据行,移动到后面页去。这就是页分裂的现象。

页分裂核心是要保证下一页的数据主键值要比上一页的要大。

3.主键索引

针对主键的索引实际上就是主键目录。主键目录就是把每个数据页的页号,还有数据页中最小的主键值放在一起,组成一个索引目录。如下图:

如果要查询id = 3 的数据,就会跟每个数据页的最小主键比较,首先id=3大于数据页1的最小主键值1,小于数据页2的最小主键值4,这样可以定位到id=3的数据一定在数据页1中,然后根据页号找到数据页。当数据页很多时,是通过二分法查找的方式来查找主键所在的数据页的。然后在数据页中二分查找定位数据,进行读取。

这样的效率是非常高的,主键目录就可以认为是主键索引。

4.B+ 树实现索引的页存储物理结构

如果表中的数据过多,就会有大量的数据页存在,对应主键目录中就要存储大量的数据页的页号和最小主键值,这种方式自然不行。

所以采用一种把索引数据存储在数据页中的方法来实现。
即表的数据存放在数据页中,表的索引也存放在页中,这个时候叫索引页。如下图:

现在有很多索引页,但是需要知道应该往哪一个索引页中去找主键数据,是索引页1还是索引页10。于是又把索引页加一个层级出来,在更高的索引层级中,保存了每个索引页和索引页中的最小主键值。如下图:

现在假设要查询id=9的数据,步骤如下:
1.会先从最顶层的索引页20开始查询,通过二分法定位到下一步应该到索引页1中去查询;
2.然后进入索引页1,通过二分法查找定位到数据应该在数据页3中;
3.进入数据页3中,就可以二分法查到id=9的数据了。

如果最顶层的索引页里存放的下层索引页的页号过多,会再一次分裂,增加高一层的索引页。如下图:

上图中多层级的索引页就是一颗B+树,属于一种树形数据结构。这就是常说的MySQL的索引是B+树组成的。

这就是索引的物理存储结构,采用跟数据页一样的页结构来存储,一个索引就是很多页组成的一个B+树。

5.聚簇索引

索引页与数据页之间是有指针连接的。索引页内部,对于同一层级内的索引页,互相之间都是基于指针组成双向链表的,如下图:

在这颗B+树中,最底层的一层就是数据页,数据页就是B+树里的叶子节点。
如果一颗B+树索引数据结构中,叶子节点就是数据页自己本身,就可以称这个B+树索引为聚簇索引。
即上图中的所有索引页+数据页组成的B+树就是聚簇索引。

聚簇索引默认是按照主键组成的,在增删改数据的时候,一方面会更新数据页,一方面会自动维护B+ 树结构的聚簇索引,更新或新增索引页。聚簇索引是默认就建立的。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5712223.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-18
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存