B-Tree

发表于 2022-06-02 更新于 2024-12-11 分类于 data_structure 阅读次数：

本文内容参考自YouTube Abdul Bari，若有错误还请指正。十分推荐观看原视频，讲得非常清晰易懂。

前言

本文将从硬盘的物理结构说起，介绍关系表中的数据如何在磁盘上进行存储和表示。并通过查询的例子，说明为什么要使用索引来加快查询。本文将从索引结构的设计角度，从m路查找树过渡到B树和B+树。

磁盘结构

一块硬盘由多个磁盘片组成，每个磁盘片像一张CD光盘一样。和CD光盘不同的是，每个磁盘片都有两面，且每一面都能够存储数据，每一面均有一个读写头去读写数据。下图为由4个磁盘片和8个读写头组成的硬盘。

对于磁盘片的每一面，都会被划分成若干个同心圆，他们被称为磁道。而每一个磁道，又会被划分成多个扇区，每个扇区的大小通常为512B。下图为盘面的示意图，由图可知，一个盘面由4个磁道组成，而每一个磁道由7个扇区构成，每个扇区大小通常为512B。

因此，如果我们知道了数据的盘面号、磁道号、扇区号，我们就能够准确定位数据所在扇区，并且能将该扇区512B的数据从磁盘读取到内存中。这种通过盘面号、磁道号、扇区号定位数据的方式称为CHS寻址。磁盘除了CHS寻址外，还有另一种寻址方式：LBA寻址。也就是说，你只需要告诉我你需要的扇区号，磁盘适配器便能从磁盘中读取所需的扇区。这种方式比CHS寻址更简洁更直观，因此本文采用扇区号的方式来代指磁盘块号。

表数据如何存储在磁盘上

假设我们要存储关系表Employee的数据，其结构如下：

CREATE TABLE Empoyee(
	id char(10),
	name char(50),
	department char(10),
	phone char(8),
	info char(50)
);

由此可知，id占用10字节，name占用50字节，department占用8字节，info占用50字节。则每插入一行数据会占用128字节的空间

下面是要进行存储的表数据，一共有100行数据要进行存储：

id	name	department	phone	info
1	John	Facebook	12345678	this guy is so nice
2	Tom	Google	12352135	good
3	Anid	...	...	...
4	Khan	...	...	...
...	...	...	...	...

由前文我们知道，一个磁盘块（即一个扇区）的大小为512字节，一行表数据会占用128字节，那么一个磁盘块能够存放4行表数据。那么对于100行表数据，我们需要25个磁盘块进行存储。

如果我们要进行SELECT * FROM Employee WHERE id = 99查询，由于没有索引信息，因此需要将磁盘块依次读入内存中，查找该磁盘块中是否含有该数据行，在最坏的情况下需要读取25个磁盘块。如果给id加上索引信息又会如何呢？

我们现在给id加上索引信息，通过id就能够知道该行表数据在哪一个磁盘块上。假设id占10字节，磁盘块号占6字节，则一行索引信息占用16字节，一个512字节大小磁盘块能够容纳32行索引信息。那么100行表数据，100/32则至少需要4个额外的磁盘块来存储索引信息。当对id加上索引信息后，我们只需要将4个索引磁盘块读入内存中然后将id与99进行比对，就能够找到对应的磁盘块号，再将数据磁盘块后读入内存就完成了数据的查找。因此，id含有索引信息后共需要读入4+1=5个磁盘块。

现在，如果我们要存储的数据行有1000行，那么需要250个数据块存储表数据，需要40个磁盘块存储索引信息。这就意味着我们又需要读取40个索引磁盘块进行查找了。那么该如何进行优化呢？与页表类似，我们可以对索引表再创建一个索引表。下图展示了该的过程。

对于40个索引磁盘块，我们只需要40/32=2个二级索引磁盘块来存储二级索引信息。当对1000行数据进行SELECT * FROM Employee WHERE id = 18;时，首要必须先读取二级索引磁盘块，它记载了某个id区间的行数据在哪个磁盘块。由于18大于1小于33，因此它的索引数据应该在1002号磁盘块。接着我们读取1002号磁盘块进入内存，通过比对id找到id=18数据行所指向的磁盘块，假设其磁盘块号为1220，那么我们只需要将1220号磁盘块读入内存就完成了数据的查找。我们一个读取了二级索引磁盘块1块、一级索引磁盘块一块、数据磁盘块一块，一共只读取了三块磁盘块。

若将该多级索引结构向右旋转，便得到了一颗树的结构，我们希望在插入数据的时候，树的结构能够自动地合并、分裂维持索引信息的正确性，这便是B树和B+树的由来。

m路查找树

在介绍B树和B+树之前，我们先来了解二分查找树和m路查找树。

上述图片描述了一棵二分查找树(Binary Search Tree, BST)。加入我们要查找14，那么先和根节点进行比较，如果小于根节点向左子树查找，大于根节点向右子树查找。14>13，因此向右查找。接着14<15，向左子树查找。最终我们找到了需要的值14。

而m路查找树就是每个节点可以有m个孩子节点，下图是一棵三路查找树。

通过查找树，我们通常能在O(logn)的时间复杂度下找到我们需要的值。那么，这些查找树是如何与数据库中的索引对于起来的呢？一般来说，树的每个节点便对应一个磁盘块。每个节点中除了存储Key值外，也会存储Value的信息，也就是磁盘块号。当我们通过m路查询树找到了id的时候，我们也就找到了对应的磁盘块号。下图是示意图。