数据结构—B树、B+树

————————————————————————————————

B树

B树的特点

1、B树的数据存储是key-value类型

2、B树的分叉——并不确定，要看具体实现

3、M阶B树：分成n个叉就是n阶B树，每个节点上最多有n-1个值

 3.1）每个节点上最多有M-1个值，并且以升序排列（2-3-4树也可以叫4阶B树）
 
 3.2）从下向上构建
1
2
3

注：2-3-4树也可以叫4阶B树
例：5阶B树：

value可以是任意数据类型
5阶B树构建示意：

为什么要有B树：

红黑树和B树比较

1、从内存的角度来说，查找时红黑树和B树哪个更好？
——>内存的主要作用是向CPU供数据
理论上：红黑树和B树时间复杂度都是O(logn)
真实情况上：
根据数据对比次数来看：cpu进行数据的判断，告诉游标向左走还是向右走
因为红黑树和B树都是在内存当中，内存向CPU提供数据的时间是相等的；

• 在B树，每一个节点都比较大，可能是十几阶，每一个节点比较的次数多；
• 在红黑树，每次比较都能折半；

在节点对比上，B树的对比次数要多；因此红黑树对比次数相对较好，所以红黑树是内存最优二叉树
2、为什么要存在B树？
因为计算机存储还有磁盘，在磁盘中，B树更优。

原因： 在磁盘当中，数据寻址浪费时间。
（在磁盘中，数据存储在磁道当中，读取数据需要磁头；因此在磁盘中，读取数据的时间=磁头移动的物理时间+平均盘面旋转半圈；）

• B树比较矮，数据寻址次数少，寻址时间较少，因此在磁盘中，B树比红黑树好
• B树多用于磁盘，原因是数据如果分成多个查询，会降低树的高度，降低寻址次数和时间。

B+树

B+树是B树的一个分支，和传统的B树不太一样
B+树被拿出来进行改造，作为mysql的专用数据库，是mysql专用底层数据结构
优势在于寻址

B+树的特点

1、B+树非叶子节点仅具有索引功能，也就是说，非叶子节点只能存储key值（只能做索引），不能存储value值；

2、B+树的所有叶子节点会构成一个有序的链表，这样就可以根据key值遍历数据。

为什么要有以上两个特点？？——>为数据库功能服务

B+树构建过程

以5阶B树为例：

查询时数据提供数据

真实的数据查询是发生在内存当中的，寻址是在磁盘当中（B+树优势在于寻址）
数据推送（提供）的顺序：磁盘——>内存——>CPU

1）没找到数据之前，选用B树查找数据（如果B树和红黑树都在磁盘中，B树找到数据的速度更快）；

2）找到后，数据需要放到内存，再传输给CPU

磁盘向cpu推送数据

磁盘每次向CPU推送一页的数据（固定的大小：4KB，如果一次推送的数据不够4KB，那么剩下的空间也不能推送）
注：
1）页是数据存储的逻辑单元；

2）假如一个文件大小为2KB，一个文件大小为3KB因此磁盘推送数据要推送和两次，一次2KB、一次3KB

3）每次磁盘寻址时间和内存推送给CPU并对比的时间如下：
内存将数据传送给CPU、CPU进行运算大约需要20ns，而磁盘一次寻址需要5ms，因此要尽量保证多在内存进行对比。

B+树的优点

1、非叶子节点只能存储key值（只能做索引），这样每次就可以使磁盘向内存中传送更多的key值，减少总体查询的时间；
（在内存当中进行数据对比，在磁盘当中进行数据查询）
（value值大小是不可控的，因此磁盘向内存同样推送4KB的数据，在B+树中，能推送更多的节点，提供更多的key值来供内存CPU做对比，减少寻址次数）

2、叶子节点是链接在一起的，有利于区间查询

例：select * from user where key >10 and key < 18
在B树需要多次查询及寻址，而由于B+树叶子节点是链表，可以在对比之后直接顺着链表查找

总结

为什么要有B树：

在磁盘中，数据存储在磁道当中，在磁盘当中，数据寻址浪费时间；B树每一层数据较多，层数比较少，数据寻址次数少，因此寻址时间较少

B树用途：

在磁盘中使用，减少寻址时间，从而减少数据查询时间。
如何使用B树：
在磁盘中使用减少寻址次数。

为什么要有B+树：

1）非叶子节点只能存储key值（只能做索引），这样每次就可以使磁盘向内存中传送更多的key值，减少总体查询的时间；
（减少磁盘寻址的时间；在查询数据时，需要从磁盘中推送数据到内存，内存再将数据传送到CPU进行判断，判断好后再根据判断的结果在磁盘寻址；）
2）虽然红黑树是内存最优结构，但是磁盘寻址耗费时间更长，因此要减少寻址次数，尽量多让内存CPU来判断。
3）叶子节点是链接在一起的，有利于mysql数据库区间查询

B+树用途：

mysql专用底层数据结构