张伦聪的技术博客 Research And Development

b树和b+树

2018-05-09

b树

性质:

  • 树种的每个节点最多拥有m个子节点且m>=2,空树除外(注:m阶代表一个树节点最多有多少个查找路径,m阶=m路,当m=2则是2叉树,m=3则是3叉);

  • 除根节点外每个节点的关键字数量大于等于ceil(m/2)-1个小于等于m-1个,非根节点关键字数必须>=2;(注:ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2)

  • 所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子

  • 如果一个非叶节点有N个子节点,则该节点的关键字数等于N-1;

  • 所有节点关键字是按递增次序排列,并遵循左小右大原则;

查找关键字:根节点开始,小于根节点关键字走左指针,大于根节点关键字走右指针,跟子节点比较关键字大小如果击中返回,未击中看走哪个指针。

插入关键字:针对一棵高度为h的m阶B树,插入一个元素时,首先在B树中是否存在,如果不存在,一般在叶子结点中插入该新的元素,此时分3种情况:

  • 如果叶子结点空间足够,即该结点的关键字数小于m-1,则直接插入在叶子结点的左边或右边;

  • 如果空间满了以致没有足够的空间去添加新的元素,即该结点的关键字数已经有了m个,则需要将该结点进行“分裂”,将一半数量的关键字元素分裂到新的其相邻右结点中,中间关键字元素上移到父结点中,而且当结点中关键元素向右移动了,相关的指针也需要向右移。

  • 此外,如果在上述中间关键字上移到父结点的过程中,导致根结点空间满了,那么根结点也要进行分裂操作,这样原来的根结点中的中间关键字元素向上移动到新的根结点中,因此导致树的高度增加一层。

假设A<C<G<H<N,在含有四个关键字ACGN的节点插入H,如空间已满,进行分裂:

分裂时切两半,中间关键字变父节点:

删除关键字:首先查找B树中要删除的元素,若元素存在,则进行删除。删除该元素后,需要判断该元素是否有左右孩子节点如果有,则上移孩子节点中的相近元素(左孩子中最右边的节点或者右孩子中最左边的节点)到父节点中去,移动之后的情况。如果没有,直接删除,移动之后的情况。

b+树

性质:

  • B+跟B树不同B+树的非叶子节点不保存关键字记录的指针,这样使得B+树每个节点所能保存的关键字大大增加;

  • B+树叶子节点保存了父节点的所有关键字和关键字记录的指针,每个叶子节点的关键字从小到大链接;

  • B+树的根节点关键字数量和其子节点个数相等;

  • B+的非叶子节点只进行数据索引,不会存实际的关键字记录的指针,所有数据地址必须要到叶子节点才能获取到,所以每次数据查询的次数都一样;

查找:刚好走大于等于索引值对应的指针 插入:查找过程找到对应叶子节点,如果叶子节点关键字没满直接插入,叶子节点关键字满了,分裂最大关键字变成父节点的一个关键字,同时叶子节点加上这个关键字 删除:直接删除


如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!

¥ 打赏博主

上一篇 分布式事务

留言