B树和B+树的理解

为了更好理解从以下几方面来说
了解二叉树，AVL树，b树的概念
b树和b+树的应用场景
为什么要用b树或者b+树来做索引结构

了解二叉树，AVL树，b树的概念

：我们都知道B树是一种多路平衡查找的树，为了更加形象了解树

所谓二叉树是指每个节点最多只支持两个分叉，相比于单向链表来说它多个一个分支
二叉查找树是在二叉树的基础上，增加规则，规则是左子树的所有子节点，都要小于它的根节点，而右子树的所有子节点，都大于它的根节点。

二叉查找树有可能会出现斜树问题，导致事件复杂度会增加，因此引入了一种叫平衡二叉树的一个机制
它具有二叉树的所有特点，同时增加一个规则，他的规则是左右两个子树的高度差的绝对值不能超过1平衡二叉树为了达到这样一个平衡所以它引入这样左旋和右旋的机制去实现树的平衡

b树是一种多路平衡查找的树，它满足平衡二叉树的规则，同时也可以有多个子树，子树的数量取决于它的关键字的数量，比如说像这个图中根节点中两个关键字3和5，那么它能够拥有的子路数量，等于关键字的数量加上1，因此从这个特征来看，在存储同样数据量的情况下，平衡二叉树它的高度一定要大于b树的
b+树其实是在b树的基础上做了增强，最大区别有两点
第一 b树的数据存储在每个节点上，而b+树种数据是存在叶子节点上，并且通过链表的方式把叶子节点的所有数据进行一个连接
第二b+树的子路数量是等于它的关键字的数量

这个就是b树的存储结构，从b树的结构上可以看到每个节点都会存储数据

所有数据是存储在叶子节点上的，并且叶子节点的数据是双向链表来关联，这个属于innoDB里面的一个特征

b树和b+树的应用场景

文件系统和数据库系统中，用来去减少磁盘IO所带来的性能损耗的一个机制，以mysql中的innoDB
为例，当我们去通过Select语句去查询一条数据的时候innoDB需要从磁盘上去读取数据，而这个过程涉及到磁盘以及磁盘的随机io。

我们知道磁盘io的性能是特别低的，特别是随机磁盘的io，为了更好的去理解为什么性能低，看一下磁盘io的工作原理，系统会把数据的逻辑地址传到磁盘，磁盘控制线路按照寻址的逻辑，把逻辑地址翻译成物理地址，也就是确定要读取的数据在哪个磁道哪个扇区为了读取这个扇区的数据需要把磁头放在这个扇区上面为了实现这样一点，磁盘会不断的去旋转，把目标的扇区旋转到磁头下面，使得磁头能够去找到对应的磁道，这里会涉及到寻道的时间以及旋转时间的一个损耗，很明显磁盘io这个过程的性能开销比较大，特别查询数据量比较多的情况下，所以在innoDb里面，干脆对存储的磁盘上的数据建立一个索引，然后把索引数据以及索引列对应的磁盘地址以B+树的方式来进行存储。

当我们需要查找目标数据的时候，根据从B+树中去查找目标数据就行了，由于B+树的子路比较多，所以只需要较少次数的磁盘IO就能够查到目标的数据

为什么要用b树或者b+树来做索引结构

原因AVL树的高度要比b树或b+树的高度要更高，而高度就意味着磁盘IO的数量，所以为了减少磁盘io的次数文件系统或数据库才会使用b树或者b+树来做索引结构