平衡二叉查找树
- 非叶子节点最多拥有两个子节点；
- 非叶子节值大于左边子节点、小于右边子节点；
- 树的左右两边的层级数相差不会大于1;
- 没有值相等重复的节点;
B树（多路平衡搜索树）
多路平衡搜索树，一棵m叉的B树特性如下：
1.排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则
2.子节点数：非叶子节点的子节点数1<n<=M ，且M>=2，空树除外（注：M阶代表一个节点最多有多少个子节点，M=M路,当M=2则是2叉树,M=3则是3叉）
3.关键字数和指针数：枝节点的关键字数量n满足ceil(m/2)-1<n<=M-1，指针数n+1（注：ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2)
4.所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子
平衡二叉树和B树区别
B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树
案例：5叉Btree，key的数量：Math.ceil(m/2)-1<=n<=m-1 ，即2<=n<=4，当n>4的时候，中间节点分裂成父节点，两边节点分裂
示例：插入C N G A H E K Q M F W L T Z D P R X Y S
- 插入C N G A
- 插入H，n>4，中间元素G向上分裂到新的节点
- 插入E K Q不需要分裂
-
插入M，中间元素M向上分裂到父节点G
GM两个key下面的3个指针，第一个指针指向<G，第二个指针指向大于G小于M，第三个指针指向大于M
- 插入F W L T不需要分裂
- 插入Z，中间元素T向上分裂到父节点
- 插入D，中间元素D向上分裂到父节点中，然后插入P R X Y不需要分裂
- 最后插入S，NPQR节点n>4，中间节点Q向上分裂，但分裂后父节点DGMT的n>4，中间节点M向上分裂
第七步的时候，上面的节点下面有5个孩子，即m叉树最多有m个孩子节点
第八步的时候，M为根节点，第三行为叶子节点，中间两个节点为非根节点和非叶子节点，最多有3个孩子，即Math.ceil(m/2)=Math.ceil(2.5)=3
第八步可以没看出来，除过第三行
B+树介绍
B+树为B树的变种，B+树和B树的区别为：
- B+树的非叶子节点只进行数据索引（只有记录的key，无具体的记录），不保存关键字记录的指针，使得B+树每个非叶子节点所能保存的关键字大大增加
- B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到
- 以下内容有争议
关键字数=非叶子节点的子节点数（分叉数）（百度百科）
关键字数=非叶子节点的子节点数（分叉数）-1（维基百科）
- B+树所有的非叶子节点都可以看做是key的索引部分
从上面图中可以看出真正全部的key信息都存储在叶子节点里面，非叶子节点里面存放的key只是起到了索引的作用，方便查询到叶子节点的key、、
由于b+树只有叶子节点保存了key信息，查询任何key都要从root走到叶子节点，所以b+树查询效率更加稳定
mysql中的B+树
mysql索引数据结构对经典的b+树进行了优化，在原有的B+树的基础上，增加一个指向相邻节点的链表指针，就形成了带有顺序指针的B+树。提高区间访问的性能
索引15虽然是存3遍，冗余，但是适当的冗余是可以接受的，索引15真正的数据data存储在叶子节点上，把数据从非叶子节点移动到叶子节点，可以让度更大
之所以有指向相邻节点的链表指针是为了方便范围查询比如>18,就可有直接将18右边的所有节点的记录取出来
B+树索引性能分析
- 一般使用磁盘I/O次数评价索引结构的优势
- 预读：磁盘一般会顺序向后读取一定长度的数据（页的整数倍）放入内存
- 局部性原理：当一个数据被用到时，其附近的数据也通常会马上被用到
- B+树节点的大小设置为一个页，每次新建节点申请一个页空间，这样就保证了一个节点物理上也存储在一个页里，就实现了一个节点的载入只需要一次I/O
- B+树的度一般会超过100，因此高度h非常小，在3到5之间
网友评论