发表于： 2017-12-08 23:41:18
1 920
今天完成的事情：
1. 深度思考一部分
2. 禅道使用整理
明天计划的事情
1. svn命令的使用
2. 深度思考一部分
遇到的问题：
无
收获：
1. m-阶B树（b+树前身）
M : 阶，就是子节点最多3个
B-tree 满足的条件
- 每个结点最多有m个孩子
- 除根节点和叶子结点外（也就是内节点），其他每个节点至少m/2个孩子
- 每个结点元素最多为m-1个
插入：
- 从最后一层开始插入，从左到右，从小到大的顺序插入
- 如果插入后节点的元素超过m-1个，就选出最中间（如果是偶数个就第m/2+1个）的一个元素，上升其父母节点，再在这个节点里排序。如果超了m-1个就在选出中间的使其上升。往复循环。
例：
1、下面咱们通过一个实例来逐步讲解下。插入以下字符字母到一棵空的B 树中（非根结点关键字数小了（小于2个）就合并，大了（超过4个）就分裂）：C N G A H E K Q M F W L T Z D P R X Y S，首先，结点空间足够，4个字母插入相同的结点中，如下图：
2、当咱们试着插入H时，结点发现空间不够，以致将其分裂成2个结点，移动中间元素G上移到新的根结点中，在实现过程中，咱们把A和C留在当前结点中，而H和N放置新的其右邻居结点中。
.jpg)
3、当咱们插入E,K,Q时，不需要任何分裂操作
.jpg)
4、插入M需要一次分裂，注意M恰好是中间关键字元素，以致向上移到父节点中
.jpg)
5、插入F,W,L,T不需要任何分裂操作
.jpg)
6、插入Z时，最右的叶子结点空间满了，需要进行分裂操作，中间元素T上移到父节点中，注意通过上移中间元素，树最终还是保持平衡，分裂结果的结点存在2个关键字元素。
.jpg)
7、插入D时，导致最左边的叶子结点被分裂，D恰好也是中间元素，上移到父节点中，然后字母P,R,X,Y陆续插入不需要任何分裂操作（别忘了，树中至多5个孩子）。
.jpg)
8、最后，当插入S时，含有N,P,Q,R的结点需要分裂，把中间元素Q上移到父节点中，但是情况来了，父节点中空间已经满了，所以也要进行分裂，将父节点中的中间元素M上移到新形成的根结点中，注意以前在父节点中的第三个指针在修改后包括D和G节点中。这样具体插入操作的完成，下面介绍删除操作，删除操作相对于插入操作要考虑的情况多点。
.jpg)
删除(delete)操作
- 首先查找B树中需删除的元素,如果该元素在B树中存在，则将该元素在其结点中进行删除，如果删除该元素后，
- 首先判断该元素是否有左右孩子结点，如果有，则上移孩子结点中的某相近元素(“左孩子最右边的节点”或“右孩子最左边的节点”)到父节点中
- 然后是移动之后的情况；如果没有，直接删除后，移动之后的情况。
- 如果删除元素之后只剩一个，（就像父节点借一个元素，树的左边节点）借最左边边的（，右边的借最右边），如果父元素有两个，借后剩一个。父节点向其丰满的子节点借一个，上移孩子结点中的某相近xaing元素(“左孩子最右边的节点”或“右孩子最左边的节点”)到父节点中
- 如果一个节点的父节点和兄弟节点都是m/2个。删除一个元素，先把父节点的借一个过来，然后移动父结点中的元素（该元素在两个需要合并的两个结点元素之间）下移到其子结点中，将这连个元素合并成一个，父元素节点只有1个的话，合并父元素节点和其子节点
进度：
禅道：http://task.ptteng.com/zentao/project-task-264.htm
返回列表
评论