DBMS - 索引
我们知道数据是以记录的形式存储的。 每条记录都有一个关键字段，这有助于对其进行唯一识别。
索引是一种数据结构技术，可根据已对其进行索引的某些属性有效地从数据库文件中检索记录。 数据库系统中的索引类似于我们在书中看到的。
索引是根据其索引属性定义的。 索引可以是以下类型 −
主索引 − 主索引是在有序数据文件上定义的。 数据文件按关键字段排序。 键域一般是关系的主键。
二级索引 − 二级索引可以从作为候选键且在每条记录中具有唯一值的字段生成，也可以从具有重复值的非键生成。
聚类索引 − 聚类索引是在有序数据文件上定义的。 数据文件按非关键字段排序。
有序索引有两种类型 −
- 密集索引
- 稀疏索引
密集索引
在密集索引中，数据库中的每个搜索键值都有一个索引记录。 这使得搜索速度更快，但需要更多空间来存储索引记录本身。 索引记录包含搜索键值和指向磁盘上实际记录的指针。
稀疏索引
在稀疏索引中，不会为每个搜索键创建索引记录。 这里的索引记录包含一个搜索键和一个指向磁盘上数据的实际指针。 要搜索记录，我们首先通过索引记录进行并到达数据的实际位置。 如果我们要查找的数据不是我们通过索引直接到达的地方，那么系统会开始顺序搜索，直到找到所需的数据。
多级索引
索引记录包括搜索键值和数据指针。 多级索引与实际的数据库文件一起存储在磁盘上。 随着数据库大小的增加，索引的大小也会增加。 非常需要将索引记录保存在主存储器中以加快搜索操作。 如果使用单级索引，则无法在内存中保存大索引，从而导致多次磁盘访问。
多级索引有助于将索引分解为几个较小的索引，以使最外层的索引非常小，以至于可以保存在单个磁盘块中，从而可以轻松地容纳在主内存中的任何位置。
B+ 树
A 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 起）被移动到新节点。
ith 键在叶子的父级重复。
如果非叶子节点溢出 −
将节点分成两部分。
在 i = ⌈(m+1)/2⌉ 处对节点进行分区。
直到 i 的条目都保存在一个节点中。
其余条目被移动到新节点。
B+树删除
B+ 树条目在叶节点处被删除。
搜索并删除目标条目。
如果是内部节点，删除并替换为左边的条目。
删除后，测试下溢，
如果发生下溢，则将条目从左边的节点分配给它。
如果无法从左侧分配，则
从节点分发到它。
如果无法从左侧或右侧分发，则
将左右节点合并到它上面。
