大家好，欢迎来到IT知识分享网。
B树，英文中的B-Tree，一个 m 阶的B树满足以下条件：
- 每个结点至多拥有m棵子树；
- 根结点至少拥有两颗子树（存在子树的情况下）；
- 除了根结点以外，其余每个分支结点至少拥有 m/2 棵子树；
- 所有的叶结点都在同一层上；
- 有 k 棵子树的分支结点则存在 k-1 个关键码，关键码按照递增次序进行排列；
- 关键字数量需要满足ceil(m/2)-1 <= n <= m-1；
下面为一个m=4的示例：
操作
既然是树，那么必不可少的操作就是插入和删除，这也是B树和其它数据结构不同的地方，当然了，还有必不可少的搜索。
假定对高度为h的m阶B树进行操作。
插入
- 新结点一般插在第h层，通过搜索找到对应的结点进行插入，那么根据即将插入的结点的数量又分为下面几种情况。
- 如果该结点的关键字个数没有到达m-1个，那么直接插入即可；
- 如果该结点的关键字个数已经到达了m-1个，那么根据B树的性质显然无法满足，需要将其进行分裂。分裂的规则是该结点分成两半，将中间的关键字进行提升，加入到父亲结点中，但是这又可能存在父亲结点也满员的情况，则不得不向上进行回溯，甚至是要对根结点进行分裂，那么整棵树都加了一层。
删除
同样的，我们需要先通过搜索找到相应的值，存在则进行删除，需要考虑删除以后的情况，
- 如果该结点拥有关键字数量仍然满足B树性质，则不做任何处理；
- 如果该结点在删除关键字以后不满足B树的性质（关键字没有到达ceil(m/2)-1的数量），则需要向兄弟结点借关键字，这有分为兄弟结点的关键字数量是否足够的情况。
- 如果兄弟结点的关键字足够借给该结点，则过程为将父亲结点的关键字下移，兄弟结点的关键字上移；
- 如果兄弟结点的关键字在借出去以后也无法满足情况，即之前兄弟结点的关键字的数量为ceil(m/2)-1，借的一方的关键字数量为ceil(m/2)-2的情况，那么我们可以将该结点合并到兄弟结点中，合并之后的子结点数量少了一个，则需要将父亲结点的关键字下放，如果父亲结点不满足性质，则向上回溯；
删除38所示
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/15169.html
