【高级数据库】第二章数据库索引

本节继续讲解数据库索引。上一节主要介绍了对顺序文件的几种索引方法，本节将引入更为常用的数据结构B-树。应用B-树做数据库索引的优势是：
（1）B-树能自动地保持与数据文件大小相适应的索引层次；
（2）对所有使用的存储块空间进行管理，使得每个块的充满成都在半满或全满之间。

第02讲 B-树

1、B-树的结构

B-树是一棵平衡树（排序树），其包含根结点、中间结点和叶子结点。每个叶子结点表示一个存储块，每个中间结点表示键值对。B-树种的结点包含：
（1）叶子结点的键对应数据文件中的键，且已排好序。由于B-树是一棵平衡树，因此每个叶子的深度是相同的，所以所有叶子结点处于同一层，另外叶子结点从左到右是有序的。
（2）每个结点都有 $n$ 个键和 $n+1$ 个指针，一般 $n>1$ 。
（3）根结点中至少有两个指针被使用。
（4）对于叶子结点中的 $n+1$ 个指针，前 $n$ 个指向数据文件的键，最后一个指针指向其右侧的下一个叶结点的最小的键对应的指针。最右侧的叶子结点的最后一个指针为空。
（5）中间结点所有 $n+1$ 个指针全部指向下一层的结点。
如图所示：

这是一个中间结点。其包含 $n=3$ 个有序键（14,52,78）和 $n+1=4$ 个指针（ $K<14, 14\leq K<52$ , $52\leq K <78, K\geq 78$ ）；如图所示：

这是一个叶子结点，其包含 $n=3$ 个有序键（57,81,95）和 $n+1=4$ 个指针（ $K=14, K=81$ , $K =95$ ）；如图所示，下面是完整的B-树：

2、B-树的查找

单键搜索： 由于B-树的每个结点的键是有序的，因此可根据待查找键与每个键进行大小对比。例如查找查找键为37的记录，则从根结点开始查找，可知37大于13，则往第二个子树。又因为37介于31和43之间，则继续往第三个子树，最后匹配到37的键，通过对应指针找到记录。如果没有找到相应的键，则可以断定当前数据文件中不存在这样的记录。
范围查找： 对于查找，可能存在范围约束。范围约束包括三种类型：有限范围 $[a,b]$ 、左无穷 $(-\infty,b]$ 和右无穷 $[a, -\infty)$ 。
（1）有限范围：首先用单键搜索方式找出 $a$ 键，若不存在则寻找比 $a$ 大的第一个键。然后在当前的叶子结点内依次向右取出相应的键，如果当前叶子结点键全部取出，则可通过最后一个指针指向右侧叶子结点。直到当前的键大于 $b$ 。
（2）左无穷：当范围没有最小值时，由于数据文件是有限的，因此可在根结点处开始，每次取最小键的指针，最后对应最左侧叶子结点的最小键，然后依次向右，直到当前的键大于 $b$ 。
（3）右无穷：与（1）相同，当取到 $a$ 后一直向右，直到指针为空。
例如查找所有记录 $[11,39]$

3、B-树的插入

树形结构相比多级索引结构更方便执行修改操作。B-树的插入部分步骤如下：
（1）首先利用单键搜索方法查找到待插入键所在的叶子结点。如果该叶子结点存在空闲空间，则直接插入即可。否则执行下一步；
（2）如果在该叶子结点中已满，我们将该叶子结点分裂成两个结点，且使得所有键分配到这两个结点中，且保证每个新结点中的键数量不低于一半。
（3）当叶子结点分裂后，上一层结点的键也需要新增，则可以按照与（2）一样的方法递归地对中间结点插入对应新键。
（4）如果在递归到根结点时，发现根结点已满，则将根结点分裂，并在上面创建一个新的根结点。

如图，当要插入键为40的记录时，（1）首先通过单键搜索方法找到其所在的叶子结点，发现已满，则将其分为两个结点，并按照每个叶子结点的键数量不小于一半原则，将新加入的40和41放入新结点。（2）由于新结点需要上一层的指针来指向它，因此需要在上一层创建新结点，考虑上一层原结点的键包括23,31和43，可知40位于31和43之间，可发现该结点也已满，所以仍需要创建新结点。（3）根结点的第二个子树中，叶子结点的最小键序列分别为13、23、31、40和43，可知上层的结点中已存在13、23、31、43，剩下40。先考虑在第二层的新结点中，若插入40，将形成40、43的键，明显不可以（第一个指针指向小于40的，这个是不存在的），所以再往上一层寻找插入40的结点，因此可插入根结点中，并将指针指向第二层新的结点。

4、B-树的删除

删除操作主要删除指定的键及相应数据文件内的记录。首先进行查找，然后将其从B-树中移除。但为了满足结点最小键数的约束，需要对删除后不满足该约束的结点进行递归的删除。

4、B-树的效率

树的高度决定查询的I/O次数；数据量一定的条件下，增大 $n$ 可以降低树的高度可以减少I/O开销，提高索引的效率，一般情况保持B-树为三层。

上一讲：数据库索引
下一讲：散列表

博客记录着学习的脚步，分享着最新的技术，非常感谢您的阅读，本博客将不断进行更新，希望能够给您在技术上带来帮助。

【高级数据库】第二章 第02讲 B-树

【高级数据库】第二章 数据库索引