算法描述

btree算法一般用于实现数据库索引，索引文件存放在磁盘中， 从磁盘中读取数据是一个很耗时的操作，所以希望每个块(block)存放的记录数越多，那么访问磁盘的次数越少。
M阶数btree每个节点最多M个子节点，那么每个节点最多M-1个元素。
M只能为奇数，不然无法均匀分裂成两个子树和父节点
根节点第一次元素个数等于M后，拆出两个子节点，所以根节点的最小子树个数=2
其他中间节点的元素个数>=M/2
当节点元素个数等于M后需要分裂，元素个数<M/2后需要调整

算法实现概述，

查询

参数：k
返回: {flag, Node, pos},flag是否查找到， 在哪个node, pos位置
描述：
从root开始，
如果 k_i = k 找到，
沿k_ < k < k_i 找到下一个节点递归查找，

插入

参数: k
调用查找算法找到插入位置，如果插入后导致元素个数等于M,那么一个节点分裂成两个，中间元素并入父节点，如果父节点元素个数也等于M，那么递归调整,如果导致根节点分裂那么产生一个新的节点，也就是btree层级升高

删除

调用搜索算法查找到元素位置，

1. 如果是中间元素，当前位置填上直接后继的值，然后问题转换成删除后继元素
2. 如果删除元素后节点元素个数>=M/2,结束，
3. 如果当前节点左右节点的元素个数>M/2,那么将父节点的元素值shift到本节点，将左的最大元素，右节点的最小元素shift到节点
4. 如果不存在3情况，那么将当前节点和父节点，兄弟节点（当前为0个子节点选右节点，其他情况选左节点），一起并入兄弟节点，如果父节点元素个数< M/2,以父节点为当前节点，递归对其调整

Posted in: java基础