文章目录

• B树系列
• • • B树的产生原因
    • B树（m路平衡多叉树）
    • • B树构建的原理
    • B树的实现
    • • Find()
      • Insert()
      • • InsertKey()
      • 中序遍历和时间复杂度
  • B+树
  • • • B+树插入分裂过程
      • 总结
    • B* 树
    • • 总结
    • B树的应用
    • • • 数据库
      • 索引
      • Myisam vs InNoDB
      • • B+树比B树的优势：
        • myIsam
        • InNoDB

B树系列

B树的产生原因

• 外查找

如果数据量本身很大，一次性无法加载到内存当中所以无法进行内查找，可以在磁盘保存数据，采用外查找。B树就可以用来进行外查找.
由于磁盘中的数据都是挨着放的，查找起来很困难。和数据库索引核心依赖的就是B树.

• 为什么不用其他的数据结构?

如果以AVL树/红黑树,平衡二叉树的形式，若每个节点存放的是指向数据在内存中的位置的指针和

关键字，每次进行关键字大小比对就行，但是可能存不下这么多关键字，所以，若每个节点存放的

都是数据的指针，在查找的过程中就要进行LogN次也就是高度次IO流的读取，进入内存当中得到

数据，进行大小的比对，CPU进行次数的读取是很快的,但是由于IO流的读取速度的是很慢的，数

据很多的话，地址也会很多，内存一样遭不住。

如果是哈希表O(1),常数次，极端情况下回造成哈希冲突很严重，效率下降很多。

• 所以可以继续优化：

让单层里面能够存的更多，平衡搜索树基础上找优化空间：

（1）二叉变成多叉（2）每一个节点多记录几行的数据，进而产生了B树

• 内查找:

B树（m路平衡多叉树）

要求满足以下性质：

1. 根节点至少是两个孩子。可能是刚被分裂出来。

2. 每个分支节点都包含K-1个关键字，K个孩子。向上取整ceil(m/2)<=K<=m.

   如果是m=10,最少是4个关键字，5个孩子。最多9个关键字10个孩子。

3. 每个叶子节点都包含K-1个关键字，由于没有孩子就不用考虑和孩子之间的关系，所以每次插入的新节点都是在叶子结点中插入，然后向上和向兄弟调整。

4. 节点中的关键字从小到大排列。

5. 每个节点的划分结构： A0,K1,A1,K2,A2,K3……Kn,An，并且从左向右是从小到大的。A是指向孩子的指针,A0指向的孩子值比K1要小，比前面的要大

以前加入一个节点存一个数据,10亿*4字节,仅仅存放地址就得4G大小空间.现在一个节点存放m个数据,同样是10亿,节点数量就变少了,需要的空间就变少了.遍历到一个节点进行IO时,这样一次读取就不是一个关键字，而是直接读m-1个人的信息。磁盘是定位到位置的速度慢，定位到位置之后读取m-1个人的信息是不慢的。

实际中M的设计为1024，这样一个节点中会存1023个关键字，1024个孩子。遍历到某一个单节点时不会是遍历查找，而是二分查找定位到K 的位置，所以是多叉搜索树。注：IO流的确定过程是慢的，但是在确定位置之后的数据读取是很快的。

B树构建的原理

为了方便插入和调整，正常开辟k-1个位置存储关键字，k个孩子。但是一般都要多开辟一个，所以是K个所以每个节点中存放孩子的指针也就是K+1个。

• 为什么要多开一个？

如果不多开一个，后续操作会变得复杂，如果插入到两个关键字的中间，不敢直接插入，得移动数据或者向上添加等，也会直接越界，变成m个关键字。所以多开一个是为了方便后续我直接插入，满了就再分裂就行。

当节点的关键字数组中存放满了之后就将分裂出一个大小一致的但是没有值的兄弟节点，但是拷贝一半的数据给到兄弟节点，将中位数提取交给父亲节点，这样自身剩下m/2-1个。如果没有父亲节点就需要创建一个新的根节点填写中位数作为左右兄弟的父亲节点来联系左右兄弟之间的关系。（这里就帮助理解为什么是m/2，和m/2-1提取一个值了）向上提取中位数交给父亲节点的过程可能会造成持续的分裂过程。

插入都是在叶子结点中进行插入，满足孩子个数总是比关键字个数多一个，满了再进行分裂，再往上提一个中位数作为关键字往父亲节点中进行插入。没满就结束了，满了就继续。为什么要提走一个？因为必须满足只少一个，多一个关键字就得多一个孩子。

持续分裂

根节点分裂产生分支节点，会增加一层，分裂的越多之后就越来越不容易分裂。也就是说在m足够大时，让根节点分裂一次所需要的节点数量是非常多的。这样，在m=1024时，仅仅三层在全满的情况下就要10亿个数据，从而体现了B树的优点，10亿个数据只需要三次IO流的确定就可以实现大大提高了效率。

天然平衡，他是向上和向右生长的。叶子结点没有孩子，不影响孩子和关键字的关系。根节点作为最顶端，2个。

B树的实现

（见代码）

插入都是插入在叶子结点，因为这样不会破坏规则,就需要先找到叶子节点的位置，叶子节点的下一层是空。

Find()

• 返回找到的节点指针和值(在节点数组M个数中的下标)。比较大小，进入下一层的左孩子右孩子.

• 在节点的sub数组中,左孩子的下标和我相等，右孩子的下标比我大一。

• 走到叶子结点还没有找到就说明是第一一次进行插入这个值。

• 希望找不到的时候，能够将叶子结点应该插入到的位置返回回来。如果找到了下标一定是大于零的，-1就说明没找到。根据这一需求设置返回值类型为pair

• _n代表的是每一个节点中的现有关键字数量。

Insert()

• 如果_root==nullptr,说明是第一次插入,新建节点并在key[]数组中放值即可.
• 先试用Find()函数查找key值,根据返回值中的second也就是下标进行判断,有就不再插入实现去重,以及确定要插入节点的指针和位置.
• 调用InsertKey()子函数,将节点指针,key值,需要新匹配的孩子节点child传入.

InsertKey()

类似于在数组中进行插入排序.节点中默认升序,如果keykeys[end],向后挪动关键字和孩子连接关系.两种情况,找到位置break以及key就是最小的,需要放在keys[0]的位置,此时end=-1,所以让keys[end+1]=key;进行赋值即可.

1. 孩子节点别忘了也连上
2. 节点中关键字总数_n别忘了++
3. 如果child不为空的情况下,更新他的爹为插入的当前节点.

• 插入完成,判断_n是否等于M,如果没满就说明插入完毕.

• 如果满了需要分裂节点时,先产生一个兄弟节点,依次将数组中一半的值的赋值给兄弟时,对应的也要将他的孩子也要给移动了即,把值拷给兄弟之后，孩子还得拷走。
• 拷走key[]数组中值的同时也将左孩子拷走,下标是相等的,完成之后还要注意还有最后一个右孩子别忘了拷走.
• 如果孩子不是空，孩子的父亲得更新为产生的brother.也就是孩子的父亲要有更新.
• 孩子都拷走了得把原来的空间中清除掉,避免空间浪费和逻辑误读.
• 移动完成之后,产生了新的根,需要判断是否是完成了根节点的分裂,那么如何判断是否是根节点呢?需要判断父亲节点是否是nullptr,所以我们需要新添加parent指针来记录.
• 如果是根节点,那么只需要将此时的cur和新产生的bronode连接起来维持关系,产生个新的根节点然后互相连接即可.
• 如果不是,就需要继续向上调整,将cur更新为parent,需要新插入的child的是broNode,新插入的值是cur->keys[mid],下一层循环继续调用InsertKey().向上调整.

中序遍历和时间复杂度

B+树

在B树的基础之上优化的多路平衡搜索树：

1. 孩子指针和关键字的数量相等,以前是M-1个关键字个数,现在的B+树可以添加M个数.

2. 分支节点的子树指针p[i]直线该关键字值大小在[k[i],k[i+1]]区间之间.

3. 所有的叶子结点都增加一个连接指针连接在一起。

4. 所有关键字及映射数据都在叶子节点中出现.

   所有的值都存在于叶子结点当中，分支节点和叶子结点有重复的值，分支节点存的是一叶子节点的索引。父亲节点存放的是叶子节点的最小值做索引.

   B+树插入分裂过程

   B+树的插入过程跟B树基本使相似的，区别是第一次插入两层节点，一层做分支，一层做根。后面的样往叶子进行插入，插入满了之后分裂一半给兄弟，以前是将中位数向上提交,现在是分裂之后的最小值向上提交作为查找时的索引值.

   转换成往父亲插入一个key和一个孩子，孩子就是兄弟，key是兄弟数组中的最小值。

   不可能在分支节点命中，分支节点只是索引而已。

总结

简化B树孩子比关键字多一个的规则,变成相等.所有的值都在叶子上,便于遍历.

B* 树

B*树是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针.节点关键字和孩子数量->[2/3*M,M].

当一个结点满时，

• 如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；

• 如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针。

B*树是B+树的变形，在B+树的非根和非叶子节点再增加指向兄弟节点的指针 。空间利用率更高的B+树。

总结

B树:有序数组+平衡多叉树

B+树:有序数组链表+平衡多叉树

B*树:一棵更加丰满,空间利用率更高的B+树

B树的应用

在内存中做内查找，B树系列和哈希和平衡搜索树对比，单纯就树的高度，搜索效率而言，B树不错。但是数据维护的越好相应的就要浪费空间，空间利用率低。插入和删除数据时为了保证维护，还涉及到分裂和合并节点，就需要挪动数据。

虽然以M为底和以2为底使得树高度更低，但是在内存中查找30次和查找3次的区别并不大。所以在内存中体现不出优势。但是在磁盘中涉及到IO，30次和3次的效率就不一样了。

数据库

B树和B+树主要应用在搜索引擎上,MyIsam InNoDB啥的.

索引

B+树的数据库中需要将磁盘中的数据索引添加到Cache/buffer中便于上层访问。B树的话关键字啥的都需要进行缓存到内存，所以意义不大。

Myisam vs InNoDB

行和列的概念:

• 建表的时候就会建立一棵B+树,索引快速查找信息.

没有主键，搜索的话就需要全表扫描，B+树比较适合做全表扫描。

一般的数据库要求主键不重复，没有字段能保持唯一的话可以用自增主键。一般的数据库不要求索引唯一，mysql建立索引可以设置使用B+树或者哈希表。

B+树比B树的优势：

1. B+树所有的值都在叶子，遍历很方便，方便进行区间查找.
2. 对于没有建立索引的字段，全表扫描的遍历更方便。
3. 分支节点只存储key，一个分支节点空间占用小，可以尽可能加载到内存。

B树不用到叶子结点就能找到值,B+树一定要找到叶子.这是B 树的优势,但是B+树高度足够低,所以差别不大.

B树的结点数据都在磁盘文件当中，访问节点都是IO行为，只是会将热数据类似于LRU原理缓存到Cache中。

myIsam

MyIsam支持全文检索，不支持事务。B+树叶子结点存放的索引文件仅仅保存数据文件记录的地址，数据文件和索引文件是分离的,非聚簇索引.

根据主键id找到节点对应索引文件，打开索引文件根据地址找到磁盘中的数据。

方面便索引树和主键树映射同样的数据.

InNoDB

InNoDB支持事务，InnoDB支持B+树索引、全文索引、哈希索引。

但InnoDB使用B+Tree作为索引结构时，具体实现方式却与MyISAM截然不同。 数据文件和索引文件是放在一起的，表数据本身就是B+树组织的一个索引结构这棵树叶子结点保存了完整的数据记录，索引中的key不是地址而是数据表的主键，聚集索引使得按主键的搜索更加高效，这是第一个区别。

第二个区别：Innodb的辅助建立索引的时候，叶子结点data域的索引文件存放的是他的主键，所以在按照辅助键来进行索引时，需要先找辅助索引的树得到主键，再用对应主键在主键索引树中检索得到记录，这样比较麻烦，因为要遍历两棵树。而MyIsam只需要遍历一遍得到地址就可以在磁盘中得到响应的数据。

叶子结点包含完整的数据记录,这种索引叫做聚集索引,因为InNoDB的数据文件本身要按主键聚集,所以InNoDB必须要有主键,如果没有显示指定,会自动选择一个可以唯一表示数据记录的列作为主键.

辅助索引data域存储响应记录主键的值,而不是地址,所有辅助索引都引用主键作为data域.