多级索引结构b

索引结构

• 当数据记录数目特别大，索引表本身也很大，在内存中放不下，需要分批多次读取外存才能把索引表搜索一遍。

• 此时, 可以建立索引的索引(二级索引)。二级索引可以常驻内存，二级索引中一个索引项对应一个索引块，登记该索引块的最大关键码及该索引块的存储地址。

• 如果二级索引在内存中也放不下，需要分为许多块多次从外存读入。可以建立二级索引的索引(三级索引)。这时, 访问外存次数等于读入索引次数再加上1次读取记录。

• 这种多级索引结构形成m叉树。树中每一个分支结点表示一个索引块, 它最多存放m个索引项, 每个索引项分别给出各子树结点 (低一级索引块)的最大关键码和结点地址。

• 树的叶结点中各索引项给出在数据表中存放的记录的关键码和存放地址。这种m叉树用来作为多级索引，就是m路搜索树。

• m路搜索树可能是静态索引结构，即结构在初始创建，数据装入时就已经定型，在整个运行期间，树的结构不发生变化。

• m路搜索树还可能是动态索引结构, 即在整个系统运行期间, 树的结构随数据的增删及时调整,以保持最佳的搜索效率。

B 树

B树的插入

• B 树是从空树起, 逐个插入关键码而生成的。

• 在B树，每个非失败结点的关键码个数都在之间（这就是植树）

• 插入在某个叶结点开始。如果在关键码插入后结点中的关键码个数超出了上界 m-1，则结点需要

• “分裂”，否则可以直接插入。

• 需要时，“分裂”可以一直进行到根结点。

• 若设B 树的高度为h,那么在自顶向下搜索到叶结点的过程中需要进行 h 次读盘。

• 在插入新关键码时，需要自底向上分裂结点，最坏情况下从被插关键码所在叶结点到根的路径上的所有结点都要分裂。

B 树的删除

• 在B 树上删除一个关键码时,
• 关键码不在叶子结点：通过用它的后继（即比它大的最小数）或前驱（即比它小的最大数）来替换，将问题转化成删除叶子中的关键码。
• 在叶结点删除关键码：
1. 删除后，关键码够数: 结束。
2. 删除后，关键码不够数: 若左（右）兄弟子树中有多余的，从兄弟子树中借一个，否则，进行合并。

1. 被删关键码所在叶结点同时又是根结点且删除前该结点中关键码个数 ，则直接删去该关键码并将修改后的结点写回磁盘。

2. 被删关键码所在叶结点不是根结点且删除前该结点中关键码个数 , 则直接删去该关键码并将修改后的结点写回磁盘, 删除结束。

3. 被删关键码所在叶结点删除前关键码个数 , 若这时与该结点相邻的右兄弟 (或左兄弟) 结点的关键码个数 ，则可按以下步骤调整该结点、右兄弟 (或左兄弟) 结点以及其双亲结点，以达到新的平衡。
1. 将双亲结点中刚刚大于 (或小于) 该被删关键码的关键码 下移；
2. 将右兄弟 (或左兄弟) 结点中的最小 (或最大) 关键码上移到双亲结点的 位置；
3. 将右兄弟 (或左兄弟) 结点中的最左 (或最右)子树指针平移到被删关键码所在结点中最右 (或最左)子树指针位置；
4. 在右兄弟 (或左兄弟) 结点中，将被移走的关键码和指针位置用剩余的关键码和指针填补、调整。再将结点中的关键码个数减1。

4. 被删关键码所在叶结点删除前关键码个数, 若这时与该结点相邻的右兄弟 (或左兄弟) 结点的关键码个数 ,则必须按以下步骤合并这两个结点。