DBMS - 索引

我们知道数据以记录的形式存储。每个记录都有一个键字段，它有助于唯一识别该记录。

索引是一种数据结构技术，可以根据已进行索引的某些属性有效地从数据库文件中检索记录。数据库系统中的索引类似于我们在书籍中看到的索引。

索引基于其索引属性定义。索引可以分为以下类型：

• 主索引 - 主索引定义在有序数据文件上。数据文件根据键字段排序。键字段通常是关系的主键。

• 次索引 - 次索引可以从候选键字段（每个记录中都有唯一值）或具有重复值的非键字段生成。

• 聚簇索引 - 聚簇索引定义在有序数据文件上。数据文件根据非键字段排序。

有序索引分为两种类型：

• 稠密索引
• 稀疏索引

稠密索引

在稠密索引中，数据库中的每个搜索键值都有一个索引记录。这使得搜索速度更快，但需要更多空间来存储索引记录本身。索引记录包含搜索键值和指向磁盘上实际记录的指针。

稀疏索引

在稀疏索引中，并非为每个搜索键创建索引记录。这里的索引记录包含一个搜索键和指向磁盘上数据的实际指针。要搜索记录，我们首先通过索引记录并到达数据的实际位置。如果我们正在查找的数据不在我们直接通过索引到达的位置，则系统开始顺序搜索，直到找到所需的数据。

多级索引

索引记录包含搜索键值和数据指针。多级索引与实际数据库文件一起存储在磁盘上。随着数据库大小的增长，索引的大小也会增长。迫切需要将索引记录保存在主内存中，以加快搜索操作。如果使用单级索引，则大型索引无法保存在内存中，这会导致多次磁盘访问。

多级索引有助于将索引分解成多个较小的索引，以便使最外层级别足够小，可以保存在单个磁盘块中，这可以很容易地容纳在主内存中的任何位置。

B⁺树

B⁺树是一种平衡的二叉搜索树，它遵循多级索引格式。B⁺树的叶节点表示实际数据指针。B⁺树确保所有叶节点保持相同的高度，因此是平衡的。此外，叶节点使用链表链接；因此，B⁺树可以支持随机访问和顺序访问。

B⁺树的结构

每个叶节点与根节点的距离相等。B⁺树的阶数为n，其中n对于每个B⁺树都是固定的。

内部节点 -

• 内部（非叶）节点至少包含⌈n/2⌉个指针，根节点除外。
• 最多，一个内部节点可以包含n个指针。

叶节点 -

• 叶节点至少包含⌈n/2⌉个记录指针和⌈n/2⌉个键值。
• 最多，一个叶节点可以包含n个记录指针和n个键值。
• 每个叶节点都包含一个块指针P，指向下一个叶节点并形成一个链表。

B⁺树插入

• B⁺树从底部填充，每个条目都在叶节点处完成。

• 如果叶节点溢出 -

  • 将节点分成两部分。

  • 在i = ⌊(m+1)_/2⌋处划分。

  • 前i个条目存储在一个节点中。

  • 其余条目（从 i+1 开始）移动到一个新节点。

  • i^th键在叶节点的父节点中被复制。

• 如果非叶节点溢出 -

  • 将节点分成两部分。

  • 在i = ⌈(m+1)_/2⌉处划分节点。

  • 最多i个条目保存在一个节点中。

  • 其余条目移动到一个新节点。

B⁺树删除

• B⁺树条目在叶节点处删除。

• 搜索并删除目标条目。

  • 如果是内部节点，则删除并用左侧条目的条目替换。

• 删除后，测试下溢，

  • 如果发生下溢，则从左侧节点分配条目。

• 如果无法从左侧分配，则

  • 从右侧节点分配条目。

• 如果无法从左侧或右侧分配，则

  • 将节点与其左侧和右侧节点合并。