赞
踩
B-树,也称为B树,是一种平衡的多叉树(可以对比一下平衡二叉查找树),它比较适用于对外查找。看下这几个概念哈:
❝❞
阶数:一个节点最多有多少个孩子节点。(一般用字母m表示)
关键字:节点上的数值就是关键字
度:一个节点拥有的子节点的数量。
一颗m阶的B-树,有以下特征:
❝❞
根结点至少有两个子女;
每个非根节点所包含的关键字个数 j 满足:⌈m/2⌉ - 1 <= j <= m - 1.(⌈⌉表示向上取整)
有k个关键字(关键字按递增次序排列)的非叶结点恰好有k+1个孩子。
所有的叶子结点都位于同一层。
一棵简单的B-树如下:
一颗3阶的B+树如下:
B+树和B-树的主要区别如下:
B-树内部节点是保存数据的;而B+树内部节点是不保存数据的,只作索引作用,它的叶子节点才保存数据。
B+树相邻的叶子节点之间是通过链表指针连起来的,B-树却不是。
查找过程中,B-树在找到具体的数值以后就结束,而B+树则需要通过索引找到叶子结点中的数据才结束
B-树中任何一个关键字出现且只出现在一个结点中,而B+树可以出现多次。
1. 在空树中插入43
这时候根结点就一个关键值,此时它是根结点也是叶子结点。
依次插入48,36
继续插入 32,发现当前节点关键字已经不小于阶数4了,于是分裂 第⌈4/2⌉=2(下标0,1,2)个,也即43上移到父节点。
继续插入37,49,前节点关键字都是还没满的,直接插入,如下:
最后插入28,发现当前节点关键字也是不小于阶数4了,于是分裂,于是分裂, 第 ⌈4/2⌉=2个,也就是36上移到父节点,因父子节点只有2个关键值,还是小于4的,所以不用继续分裂,插入完成
InnoDB一棵B+树可以存放多少行数据?
为什么索引结构默认使用B+树,而不是hash,二叉树,红黑树,B-树?
B-树和B+树的区别
点个 在看你最好看
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。