B树
抛砖引玉
为什么要深入学习B+树,因为在学习mysql时候知道了innodb存储引擎和myisam存储引擎存储数据的结构用到了B+树,为什么要用B+树?
一旦打开了知识的大门,发现学习的内容还有很多,学无止境!!!
好多好多树呀
学习B+树之前先要学习B树,学习B树之前又要追溯到二叉树
别着急慢慢来,我是这么安慰我自己的!!
二叉树
什么是二叉树?
简单来说二叉树是一种存储数据的结构,问我们之前学习的哈希表,链表,数组一样都是存储结构的一种;今天主要聊的是二叉树以及二叉树的变种;
二叉树百科定义
二叉树的几种形态
- 空树;
- 只有根节点的树;
- 只有左子树;
- 只有右子树;
- 完全二叉树;
如下图所示—
在普通二叉树的基础上衍生出了BST俗称二叉查找树
BST是怎样插入数据的?
以数据 10,6,4,7,3,8,2,9,1,5 按顺序插入二叉树为例
BST是怎样查找数据的?
以上图数据为例,
查找数据5是怎样查找的呢?
还是上图的数据如果是在线性表结构中是怎样查找的呢?
对比分析,BST查找数据比线性表在一定程度上要好一些,但是如果是二叉树的极端情况(递减或者递增数据)----只有左子树或者右子树,那么二叉树就会退化成线性表结构;
如下数据1,2,3,4,5如果查找数据5
基于以上原因,因此就有了基于BST的一些变种形式B树,AVL树,B+树,等;
BST插入数据是比较繁琐的,不如线性表,但是查找效率要好于线性表(非极端情况下)
BST是怎样删除数据的?
假如要删除3,先找到3,然后删除,如果有子节点,则子节点来补位
线性表中可以通过下标来直接将元素删除;
综上分析-----
如果插入/删除数据比较频繁,BST的插入/删除效率不如线性表,但实际情况中是有些数据录入之后很少修改,反而是查询的次数远远大于修改的次数,因此BST可应用的场合是插入不频繁但是查询频繁的场景;
总结----BST的特征:
- 任意结点（包括根结点）的左子树上的结点的值都比这个结点得值小。
- 任意结点（包括根结点）的右子树上的结点的值都比这个结点得值大。
- 对一个二叉树进行中序遍历，如果是单调递增的，则可以说明这个树是二叉搜索树。
二叉树的遍历----四种方式
- 前序遍历----先访问根节点,在前序遍历左子树;
- 中序遍历----先访问左子树,然后访问根节点,再访问右子树;
- 后序遍历----先访问左子树,在访问右子树,最后访问根节点;
- 层序遍历-----从根节点往下一层一层访问;
代码实现----
先建立一颗二叉树
package TreeB;
import java.util.LinkedList;
public class BinaryTreeD {
public int data;
public BinaryTreeD leftBTree;//左节点
public BinaryTreeD rightBTree;//右节点
//二叉树构造方法
public BinaryTreeD(int data) {//这里应该是泛型,但为了简便只好先这样
this.data = data;
}
//创建一个二叉树----为了简便指定为Integer 其实应该是泛型的
/*
将链表的数据加入到二叉树中
*/
public static BinaryTreeD createBinaryTree(LinkedList<Integer> list) {
BinaryTreeD binaryTreeD = null;
//如果链表为空
if (list == null || list.isEmpty()) {
return null;//空树
}//如果 不为空,则添加元素,首先要从list中取数据,
Integer data = list.removeFirst();
if (data != null) {//如果data不为null则添加,----因为Integer不像int,是有可能出现null值的
//添加数据
binaryTreeD=new BinaryTreeD(data);
//下一个添加的元素左节点,右节点,都是这样操作,因此递归掉用就可以了,出口是list==null,return null;
binaryTreeD.leftBTree=createBinaryTree(list);
binaryTreeD.rightBTree=createBinaryTree(list);
}
return binaryTreeD;
}
//前序遍历二叉树 跟节点----左子树----右子树
//因为要遍历,把树当作参数传进来
public static void preOrderBinaryTree(BinaryTreeD binaryTreeD){
//如果树为空
if(binaryTreeD==null){
return;
}
//递归方法,出口是binaryTreeD==null
System.out.print(binaryTreeD.data+"\t");
preOrderBinaryTree(binaryTreeD.leftBTree);
preOrderBinaryTree(binaryTreeD.rightBTree);
}
//中序遍历 左子树----根----右子树
public static void midOrderBinaryTree(BinaryTreeD binaryTreeD){
//如果树为空
if(binaryTreeD==null){
return;
}
//递归方法,出口是binaryTreeD==null
midOrderBinaryTree(binaryTreeD.leftBTree);
System.out.print(binaryTreeD.data+"\t");
midOrderBinaryTree(binaryTreeD.rightBTree);
}
public static void bacOrderBinaryTree(BinaryTreeD binaryTreeD){
//如果树为空
if(binaryTreeD==null){
return;
}
//递归方法,出口是binaryTreeD==null
bacOrderBinaryTree(binaryTreeD.leftBTree);
bacOrderBinaryTree(binaryTreeD.rightBTree);
System.out.print(binaryTreeD.data+"\t");
}
public static void main(String[] args) {
LinkedList<Integer>list= new LinkedList<>();
list.add(10);
list.add(6);
list.add(4);
list.add(7);
list.add(3);
list.add(8);
list.add(2);
list.add(9);
list.add(1);
list.add(5);
BinaryTreeD binaryTree = createBinaryTree(list);
preOrderBinaryTree(binaryTree);
System.out.println();
midOrderBinaryTree(binaryTree);
System.out.println();
bacOrderBinaryTree(binaryTree);
}
}
H代表树高,N代表元素个数;
来看BTS树查找数据的时间复杂度
仅算最坏查找的时候(空树,查找啥数据???所以不算)
1,深度为1的BTS,即只有根节点,查找次数为1,
2,深度为2的BTS,查找次数为2;
3,深度为3的BTS树,查找次数为3;
4,深度为4的BTS树,查找次数为4
以此类推,二叉查找树查找数据的时间复杂度为O(H);
来看BTS树插入数据的时间复杂度
仅算最坏插入的时候(空树插入就完了,不用判断是插入左边还是右边)
1,深度为1的BTS树.判断一次(即插入左边还是右边)
2,深度为2的BTS树,判断两次,(根节点一次和左节点(或者右节点)一次)
3,深度为3的BTS树,判断三次
以此类推,二叉查找树的插入数据的时间复杂度为OH);
来看BTS树删除数据的时间复杂度
删除数据是要先查找到该数据,所以查找(O(H))之后删除(1),所以时间复杂度也是O(H)
由以上可看到BTS树的时间复杂度跟树的高/深度有关;
但是------->极端情况下如下图的BTS树
这时候BTS树就退化成了链表,这时候时间复杂度就成了O(N)-----N指元素个数,一般情况下树的高度H是小于元素个数N的;
但是当数据量足够多的时候------>趋于无穷大则可以看作是O(H)/O(N)=1;
所以当插入的数据量很大的时候,树的深度(高度)会非常大,于是二分查找树数据查询效率其实也不算高,于是就衍生出了基于BST的AVL树----平衡二叉查找树
AVL树
什么是AVL树呢?
在计算机科学中，AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。
特点:除了具备二叉查找树的特点,他还具有书中任何节点的两个子树的高度差最大差别为1,以避免二分查找树中的极端情况;
还是之前的数据----- 10,6,4,7,3,8,2,9,1,5 按顺序插入
可以发现AVL树在插入相同数据的情况下树的高度变小了,那么树的高度变小了有什么好处呢???待会在说这个,先说一下AVL树的其他方面:
AVL树的失衡状态>>>>**
由上图可以发现AVL在树失衡的时候做了一些操作(旋转)使得树能过够保持一个平衡状态,那么我们来研究一下什么状态下树会失衡呢?
看图,以上是左子树失衡的两种情况,
特点是插入或者删除数据后使得根节点的左子树的高度比右子树高度高2,因此失衡了;
反过来讲就是怎么使得失衡的树保持平衡?
以做左子树失衡为例,要么删除元素使得根节点左子树高度减少以使得与右子树高度差不大于1(即减少根节点左子树高度),要么添加元素使得根节点右子树高度增加以使得与左子树高度差不大于1;
同理可以得到右子树的失衡的两种情况
右左子树失衡和右右子树失衡-----对称过来就可以了;
还是上图吧------
AVL树中的旋转>>>>>>
AVL树的旋转由树的失衡引起的,(上面四种树的失衡)
先看第一种左左子树失衡和右右子树失衡------>
所以可以总结为由于插入或者删除元素引起的树失衡
剩余两种失衡
单纯的旋转并不能解决问题,需要进行两次旋转
由此可以看到AVL树的插入或者删除都有可能通过旋转来调整来维持树的平衡
AVL树本质上还是一棵二叉搜索树，它的特点是： [1]
1.本身首先是一棵二叉搜索树。
2.带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。
也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。
二叉平衡树的实现代码>>>>>>
比较复杂,感兴趣你自己组找资源吧!
AVL树的效率-------->>>>>
从插入数据上讲----
除了要比较大小,还要做旋转操作,因此插入效率上讲不如二叉排序树----BTS
从查找数据上讲—
AVL树避免了BTS中出现的极端情况,所以查找数据的最坏效率要比BTS树的最坏效率要高;
AVL树的时间复杂性:O(logn)
网上有一个题目是------AVL树能插入的最少节点数的复杂度;
假设一棵树的深度为h,根节点左子树高度为h-1,根节点右子树的高度h-2(也有可能是h-1但这是一颗完全平衡的AVL树,由于是最少节点,所以选择深度为h-2),
假设T(h)为高度为h的AVL树能放的最少节点,那么就有如下关系
T(h)=左子树节点+右子树节点+根节点
由此推出 T(h)>T(h-1)+T(h-2)-------->>>>>
由于高度减少2,则节点数量减半(由于式不完全的树,要是完全的树是高度每减少1,节点数量减半)------>>>>
左子树节点数------2^(h-1) -1
右子树为2^(h-2)-1,但是由于是最少节点,所以右子树为非完全的树,所以
就有了以下不等式
T(h)>2(T(h-2))
T(h)>2i(T(h-2i)
i=i/2
递推得到
T(h)>2^(h/2)
logT(h)>h/2
h<2logT(h)所以树的高度不超过2logT(h)
B树
什么是B树?
B树(BalanceTree)也是二叉树的改进的一种,又叫多路平衡查找树,在AVL树的基础上又加了一些约束,B树的特点是:
（1）排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则；
（2）子节点数：非叶节点的子节点数>1，且<=M ，且M>=2，空树除外（注：M阶代表一个树节点最多有多少个查找路径，M=M路,当M=2则是2叉树,M=3则是3叉）；
（3）关键字数：枝节点的关键字数量大于等于ceil(m/2)-1个且小于等于M-1个（注：ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2);
（4）所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子; -----来自百度百科
B树的图解------>>>>>
B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树（查找路径不只两个），数据库索引技术里大量使用者B树和B+树的数据结构，
B树的阶数或者称为度数,看图找规律—可以看到跟之前的二叉树和AVL树不同的是B树的一个节点种可以存放的值可以不为一个,这样在存储数据量相同的的情况下B树的深度就减少了;
B+树
什么是B+树
B+树是B树的一种变形形式，B+树上的叶子结点存储关键字以及相应记录的地址，叶子结点以上各层作为索引使用。一棵m阶的B+树定义如下:
(1)每个结点至多有m个子女；
(2)除根结点外，每个结点至少有[m/2]个子女，根结点至少有两个子女；
(3)有k个子女的结点必有k个关键字。
B+树的查找与B树不同，当索引部分某个结点的关键字与所查的关键字相等时，并不停止查找，应继续沿着这个关键字左边的指针向下，一直查到该关键字所在的叶子结点为止.--------来自百度百科
B+树的每个节点可以包含更多的节点,这样做的原因是 为了降低属的高度,第二个原因是将数据范围变为多个区间,区间越多,检索数据越快;
非叶子节点存储key,叶子节点存储key和数据
叶子节点两两指针相互连接,符合磁盘的预读性特征,顺序查询的性能更高;
下图为B树和B+树的图解
接下来看一下各种树存储数据的方式图解-------
以10,6,4,7,3,8,2,9,1,5 为例看相同的数据在不同的树存放数据的区别
可以看到在同样的数据量下,B树和B+树的树深小,这样有什么好处呢?
也是接上面的问题,
关于B树和B+树的区别放在数据库中去说明一下----
以三阶B树为例子-------
B树--------------->>>>>B树存储数据结构图
可以看到B树的存储结构-----在一个磁盘块中存放了指针和key和value,
B+树------>>>>>>>>>B+树存储数据结构图
可以看到B+树的非叶子节点存储的是key和指针,在叶子节点中存放了数据,
我们可以做一个假设,但是再假设前我们要明白两点-----
局部性原理-----
空间局部性-----------即数据跟程序都有聚集成群的倾向,我们希望把具备某一些特征的数据存放在一起;
时间局部性---------即被访问过一次的数据下一次很有可能被在次访问;
磁盘预读------
磁盘预读------加入你想让电脑给你从一篇文章种查找字母"A",虽然电脑给你找到了字母A,但是实际上电脑并不是仅仅读取了字母A一个字符,而是很多内容------即每次读取磁盘获取数据并不是仅仅读取我们需要的数据而是读取一部分数据------具体来说就是内存和磁盘交互时会有一个叫页的单位,每次至少读取4K,可以时8K,16K,总之时4K的整数倍;
回到B树和B+树的数据结构图
假设提条数据data为1KB;key和指针不占空间
在mysql中 innodb存储引擎一次IO读取的数据大小为16KB;
那么问题来了,在B树中要查找数据70需要左多少次IO呢?
第一次内存中读入磁盘块1,70在56和88之间,于是第二次IO读取磁盘块3
70在66和77之间,第三次IO读取磁盘块8,在磁盘块8找到了数据;
三次IO,读取数据48KB;
那在这48KB中能存放多少数据呢?
161616=256条数据,那么三次IO能查找的数据也只有256条,实际会少于256条,因为key和指针不可能不占空间;
如果上面换成是B+树,IO次数不变,变得是在B+树中非叶子节点存放的是key和指针,不存放数据,于是三次IO读取的数据量也是48KB,但是可以查找的数据量是多少呢?
假设一组key和指针占10字节,
那么可以查找到的数据量--------
160010241600102416=4,294,967,296----千万级别的数据量了,
但问题的关键是key占的大小是不确定的,所以在设立索引的时候索引的长度也影响数据的能查找的量级,如varchar索引和int索引都能找到数据的树是推荐int的,尽量避免全文索引等;
再来一个小问题-----
在一个表中id为主键索引,是否一定要设置成自增呢?
最好设置成自增
原因----除了提高查找效率外还由一个重要的原因
