本文是为了在原有b+树索引情况下做一些拓展。

1.B+树文件组织

  为什么要用索引结构？顺序索引随着数据变大，查找效率会严重降低；随着文件增大，增加的索引记录占百分比和实际记录之间变得不协调，不得不存储在溢出块之中。我们通过在文件上使用B+数索引来解决存储实际记录的性能下降问题。我们不仅把B+树作为索引使用，还会把B+树作为文件中记录的组织者。在B+树文件组织中，树的叶节点存放的是记录而不是指向记录的指针。下图为该文件结构的例子。
由于一个记录通常比指针大，因此一个叶节点中能存放的记录数目通常要比一个非叶节点中能存储的指针数目少。然而，叶节点仍然要求是半满的。

b+树文件结构

1.1B+树文件结构插入与删除

  B+树文件组织中记录的插入和删除与B+树种索引项的插入与删除处理方式一致。当插入一条记录有给定码值v的记录，系统通过B+树中查找 小于等于v的最大码来定位应该包含该记录的块。如果定位到的块有足够大的空间来存放记录，系统就将该记录存放在该块中。否则，就像B+树的插入那样，系统就将该块分为两个，重新分布其记录(按照B+树值的顺序),以给新纪录创建空间。这种分裂以通常的形式在B+树中自底向上传播。

  当删除一个记录的时候，系统首先从包含它的块中将其删除。如果块b 因此不到半满，就要对B的记录和相邻的块C中的记录重新分布。假定记录大小固定，每个块包含的记录数至少是它所能包含的最大记录数的一半。

  当我们用B+树作为文件组织方式时，空间的利用尤其重要，因为记录所占的空间很可能比码和指针所占的空间要大得多。通过在分裂和合并时在重新分布中涉及更多的兄弟节点，我们可以改善B+树的空间利用率。

  在插入时，如果某个节点已满，系统就会尝试把它的一项重新分布到与它相邻的节点中，以给新项腾出空间。如果因为相邻节点本身已满导致这种尝试失败，系统就要分裂该节点，并在一个相邻节点和分裂原始节点得到的两个节点均匀分配所有项。由于这三个节点总关包含的项比两个节点所能多容纳1个，因此每个节点约是2/3满的。更准确的说，每个节点至少有2n/3个数据项(其中n是能容纳的最大项数)

  在删除的时候，如果节点中项少于[2n/3]，系统就会试图从相邻的节点借入一项。如果两个兄弟节点都有 [2n/3]条记录，那么系统就不是借入一项，而是把这个节点以及两个星弟节点中的所有项均匀的分布到两个几点钟，并且删除第三个节点。我们能用这个方法 因为项的总是是 3[2n/3] -1,当我们采用哪个三个节点进行重新分布情况下，每个节点能保证 [3n/4]项。一般地，如果重新分布涉及m个节点(m-1）个兄弟项，那么 每个节点至少能保证 [(m-1)n/m]个索引项。然而，参与重新分布的兄弟节点越多，代价越高。

  在b+树文件组织中，树的相邻叶节点可以分布在磁盘中不同位置。当一个文件组织最初建立在一组记录上的时候，可以实现把磁盘整基本连续的块分配给树中连续的叶节点。由此对叶节点的顺序扫描就相当于在磁盘上的顺序扫描。随着在树中不断进行插入和删除操作，这种顺序性逐渐丢失，对叶节点的顺序访问也需要越来越频繁的磁盘寻道。为了修复顺序性，需要对索引重建。

  b+树文件组织可以用于存储大型数据对象，如SQL clob类型和blob类型，这些数据对象可能比磁盘块还大，甚至是好几个GB。那么大的数据对象可以通过拆分成小份文件 并且记录序列 组织成b+树文件组织进行存储。拆分的记录可以按序编号，或者根据记录在大型对象中字节偏移量进行编号，这样记录的编号就可以用于搜索。

2.辅助索引和记录重定位

  一些文件组织(如b+树文件组织)可能改变记录的位置，即使记录没有更新。举例来说，当b+树文件组织中的一个叶节点分裂，一些记录会移动到最新的节点中。在这种情况下，所有存储了那些指向重定位过的记录 的指针就需要更新，即使记录中的值不曾改变。每个叶节点可能包含相当多的记录，而其中每条记录都可能在每个辅助索引中的不同位置。因此一个叶节点的分裂可能需要几十上百次io来操作所有影响到的辅助索引。
   如果 我们在辅助索引中，不记录具体 地址，只记录聚簇索引的值，那么 我们就不需要每次都去监听io变动，只需要在该聚簇索引值变动的情况下，改动辅助索引即可。但是这样会导致通过辅助索引查询，需要查两次(先通过辅助索引查主索引值，再通过主索引去查对应数据)

3.字符串上的索引

   字符串有以下几个特性1.变长 2.字符串可能很长 所以会有以下几个问题 1.节点是满的，但是由于索引所占位置不同，扇出不同 2.扇出可能比较小。
   如何解决这两个问题呢？可以用一种前缀压缩的算法，其实就是吧字符串只存储每个搜索码值的一个前缀，使得这个前缀足以将由该搜索码值分开的两棵子树中的码区分开。

   例如在 如果我们数据库里面的某个子树中已经有两个索引值分别为haha 与 hehe 我们再该节点中插入一条记录为 hahe2332442234 ，这种情况下 我们可以只存储 hahe来标志索引。

4.B+树索引 批量加载

   假如 我们在一张表中原有1亿条记录 。现在插入一条记录，那么这个任务的代价是什么呢？
   很明显 假如每个节点扇出为100 那么1亿条记录的b+树索引深度为 4.每次插入最优情况下需要5次io 并且还有额外的消耗。
   假设现在该表中有1亿条记录，我们需要往里面插入100万条记录。那么我们就需要5亿次io操作 并且都是随机io来进行操作。假设每次随机io消耗时间10ms 那么共计500万秒时间来进行操作 很明显这个开销太大了。相比 如果 该条记录占用100字节，磁盘系统可以美秒50mb的速度进行传输，那么只需要200s来读取整个关系。
   当遇到大量项第一次插入到索引中称为索引的批量加载，当遇到这种批量加载情况下，我们采用如下方法来进行优化

1. 创建一个含有关系索引的临时文件。
2. 根据构件好的索引的搜索码来排序文件。
3. 扫描排序好的文件并且将其插入到索引中。

   当b+树为空的时候，我们甚至可以采用上述方法自底向上的快速构建树,这种方法称为自底向上b+树构建

5.总结

1. b+树文件组织
   目的:1.防止随着文件增大。查找的复杂度线性上升O(N) 2.防止数据查找会发现数据块的溢出现象。
   手段:1.简历b+树索引，管控内存 块 每行8k 每2行1页与存储设备16k一致
2. 辅助索引与索引重定位
   目的:帮助辅助索引查找到记录的手段 。防止辅助索引需要无时无刻监听io磁盘变动。防止变更开销过大。
   手段: 让辅助索引存储主索引值，而不是记录的地址。
3. 字符串上的索引
   目的:1.防止节点是满的，但是由于索引所占位置不同，扇出不同 2.防止扇出可能比较小。
   手段：前缀压缩
4. b+树批量加载
   目的：大数据量加载到索引结构中的时候，比较慢，消耗比较大。提升性能与计算消耗。
   手段：顺序读取后批量插入。