DBMS - 索引

我们知道数据是以记录的形式存储的。 每条记录都有一个关键字段,这有助于对其进行唯一识别。

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

索引是根据其索引属性定义的。 索引可以是以下类型 −

  • 主索引 − 主索引是在有序数据文件上定义的。 数据文件按关键字段排序。 键域一般是关系的主键。

  • 二级索引 − 二级索引可以从作为候选键且在每条记录中具有唯一值的字段生成,也可以从具有重复值的非键生成。

  • 聚类索引 − 聚类索引是在有序数据文件上定义的。 数据文件按非关键字段排序。

有序索引有两种类型 −

  • 密集索引
  • 稀疏索引

密集索引

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

Dense 密集索引

稀疏索引

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

Sparse 稀疏索引

多级索引

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

Multi-level 多级索引

多级索引有助于将索引分解为几个较小的索引,以使最外层的索引非常小,以至于可以保存在单个磁盘块中,从而可以轻松地容纳在主内存中的任何位置。


B+

A B+ 树是遵循多级索引格式的平衡二叉搜索树。 B+ 树的叶节点表示实际的数据指针。 B+ 树确保所有叶子节点保持在相同的高度,从而保持平衡。 此外,叶节点使用链表链接; 因此,B+ 树可以支持随机访问和顺序访问。

B+树的结构

每个叶节点与根节点的距离相等。 B+ 树的顺序为 n,其中 n 对于每个 B+ 都是固定的 树。

B+ 树

内部节点

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

叶节点

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

B+树插入

  • B+树从底部开始填充,每个条目都在叶子节点完成。

  • 如果叶节点溢出 −
    • 将节点分成两部分。

    • i = ⌊(m+1)/2⌋. 处的分区

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

    • 其余条目(i+1 起)被移动到新节点。

    • ith 键在叶子的父级重复。

  • 如果非叶子节点溢出 −

    • 将节点分成两部分。

    • i = ⌈(m+1)/2 处对节点进行分区。

    • 直到 i 的条目都保存在一个节点中。

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

B+树删除

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

  • 搜索并删除目标条目。

    • 如果是内部节点,删除并替换为左边的条目。

  • 删除后,测试下溢,

    • 如果发生下溢,则将条目从左边的节点分配给它。

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

    • 从节点分发到它。

  • 如果无法从左侧或右侧分发,则

    • 将左右节点合并到它上面。