从磁盘结构到数据库索引

磁盘结构

从磁盘结构到数据库索引

按照顺时针方向,一个盘片由很多section组成,编号0-N。从里向外分,又由多个track组成,编号0-N,sectiontrack交叉的地方叫做block,所以一个block可以由sectiontrack来定位。每一个block的大小是一样的。

操作系统读取数据都是按照block为单位进行。

block内,数据的存储结构可以看成一个一维数组,大致结构是这样(假设一个blocksize512byte)

从磁盘结构到数据库索引

Disk的读写头可以旋转和伸缩来定位一个block

为了使磁盘中的数据可以被应用程序使用,必须先copy数据到随机读写存储器RAM中,而这正是耗时的操作。

磁盘如何存储数据库数据

假设现在有一个Employee表,其中有一些字段,如下所示,所以一行数据的大小是128byte

从磁盘结构到数据库索引

假设总共有100行这样的数据

从磁盘结构到数据库索引

所以每一个block可以存储4行这样的数据,这100行数据需要25个block,假设现在按照这样的方式来查询一条记录,最多需要查找25个block.

那索引为什么可以减少查找的次数呢?

什么是索引

我们建一个简单的索引,有两个字段,一个eid,表示Employeeid,还有一个字段pointer,指向数据存储在Disk上的位置。empolyee中的每一行,在index上都有一条记录

从磁盘结构到数据库索引

当然我们也需要考虑如何存储这个索引表。如果索引存放在Disk上,那么这个索引需要占据多少个block呢?eid大小为10bytespointer大小为6bytes,所以一行索引就有16个bytes大小。100条索引就需要占据100 * 16 / 512,也就是 4个block

在现在的情况下,我们查找Employee表中的一条数据,最多就只需要4次索引表查找和一次Employee表读取,相比没有索引的情况效率提升了很多

多级索引

如果现在把Employee表中的数据行数增加到1000行,那么同理,数据表需要250个block,索引表需要40个block,现在查询一条记录就最多需要41次block的读取和拷贝(IO)

根据建立索引可以减少查找次数的理论,我们现在可以建立二级索引,也就是对上面的一级索引再建立索引,二级索引存储一级索引所在的block,现在一级索引占用40个block,所以二级索引表有40条记录,每一个索引记录大小为16byte,所以二级索引占用的block40*16/512,也就是2个block。那么现在再来根据二级索引查找到一级索引所在的block,再根据一级索引直接定位到Employee表中的某条数据所在的block,最多一共需要2+1+1=4次查找(IO),相比之前效率又提升了不少。

从磁盘结构到数据库索引

随着数据表中数据记录的增加,可以建立三级,四级....索引来减少IO次数

多路(n-way)搜索树

二叉搜索树

每个节点只有一个值,一个节点最多两个子节点,左子节点比父节点小,右子节点比父节点大

从磁盘结构到数据库索引

一颗树代表了某一级索引,搜索树的高度(深度)代表了最多IO的次数,所以减少树的高度可以减少IO的次数

思路就是一个节点存储多个值,相应的子节点最大个数也可以有多个

n-way搜索树

由二叉搜索树扩展,让每个节点最多可以存n-1个索引值,每个节点可以有n个子节点,就是n-way搜索树

从磁盘结构到数据库索引

上面就是一个3路搜索树

我们可以使用这样的数据结构来作为索引,但是n-way搜索树也存在一些问题

比如现在有三个数据:10,20,30,要用一个10-way搜索树来构建。很有可能,最终会构建出一个这样的树

从磁盘结构到数据库索引

这是一种最坏的情况,相当于退化成链表结构。

B树:多路搜索树上增加限制

B树,实际上可以看作是n-way搜索树 + 规则(如何构建这棵树的规则)

规则:

  • 每个节点至少有[n/2]个子节点
  • 根节点可以最少有2个子节点
  • 所有的叶子节点必须在一个层级
  • 创建过程是由下往上的

值:10,20,40,50。要构建一个4-way搜索树。4-way搜索树,意味着一个节点最多可以有3个值。

从磁盘结构到数据库索引

继续插入操作,最后形成的结果是:

从磁盘结构到数据库索引

每一个节点可以有多个值,每个值里面包含一个键和位置指针,键用来作为标识,数据值标识数据存放的位置

B+树

B+树中,不是每个值旁边都有一个指向数据存储位置的指针,只有叶子节点才有。非叶子节点的值,在叶子节点上有他的副本

从磁盘结构到数据库索引

相关推荐