https://zhuanlan.zhihu.com/p/59788528 https://mp.weixin.qq.com/s/wiqfcVrsLgLvLbsTU-qSag ## B树 一棵m阶的B-Tree有如下特性 1. 每个节点最多有m个孩子，m称为b树的阶 2. 除了根节点和叶子节点外，其它每个节点至少有Ceil(m/2)个孩子 3. 若根节点不是叶子节点，则至少有2个孩子 4. 所有叶子节点都在同一层，且不包含其它关键字信息 5. 每个非终端节点包含n个关键字（健值）信息 6. 关键字的个数n满足：ceil(m/2)-1 <= n <= m-1 7. ki(i=1,…n)为关键字，且关键字升序排序 8. Pi(i=1,…n)为指向子树根节点的指针。P(i-1)指向的子树的所有节点关键字均小于ki，但都大于k(i-1)  每个节点占用一个盘块的磁盘空间，**一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，指针存储的是子节点所在磁盘块的地址**。两个键将数据划分成的三个范围域，对应三个指针指向的子树的数据的范围域。以根节点为例，关键字为17和35，P1指针指向的子树的数据范围为小于17，P2指针指向的子树的数据范围为17~35，P3指针指向的子树的数据范围为大于35 模拟查找关键字29的过程： 1. 根据根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】 2. 比较关键字29在区间（17,35），找到磁盘块1的指针P2 3. 根据P2指针找到磁盘块3，读入内存。【磁盘I/O操作第2次】 4. 比较关键字29在区间（26,30），找到磁盘块3的指针P2 5. 根据P2指针找到磁盘块8，读入内存。【磁盘I/O操作第3次】 6. 在磁盘块8中的关键字列表中找到关键字29 分析上面过程，发现需要3次磁盘I/O操作，和3次内存查找操作，由于内存中的关键字是一个有序表结构，可以利用二分法快速定位到目标数据，而3次磁盘I/O操作是影响整个B-Tree查找效率的决定因素。 **B-不利于范围查找，比如上图中我们需要查找\[15,36\]区间的数据，需要访问7个磁盘块（1/2/7/3/8/4/9），io次数又上去了，范围查找也是我们经常用到的，所以b-树也不太适合在磁盘中存储需要检索的数据。** ## B+树  #### **b+树的特征** 1.每个结点至多有m个子女 2.除根结点外,每个结点至少有\[m/2\]个子女，根结点至少有两个子女 3.有k个子女的结点必有k个关键字 4.父节点中持有访问子节点的指针 5.父节点的关键字在子节点中都存在（如上面的1/20/35在每层都存在），要么是最小值，要么是最大值，如果节点中关键字是升序的方式，父节点的关键字是子节点的最小值 6.最底层的节点是叶子节点 7.除叶子节点之外，其他节点不保存数据，只保存关键字和指针 8.叶子节点包含了所有数据的关键字以及data，叶子节点之间用链表连接起来，可以非常方便的支持范围查找 #### **b+树与b-树的几点不同** ##### **核心区别:** B+树只有**最底层**的**叶子节点**才**保存数据**，其他的都是非叶子节点，只保存关键字和指针，这样使得**非叶子节点存储的数据更多**，使树变矮，这样内存中可以**存储更多的指针**，**减少磁盘IO** b+树中一个节点如果有k个关键字，最多可以包含k个子节点（k个关键字对应k个指针）；而b-树对应k+1个子节点（多了一个指向子节点的指针） b+树除叶子节点之外其他节点值存储关键字和指向子节点的指针，而b-树还存储了数据，这样同样大小情况下，b+树可以存储更多的关键字 b+树叶子节点中存储了所有关键字及data，并且多个节点用链表连接，从上图中看子节点中数据从左向右是有序的，这样快速可以支撑范围查找（先定位范围的最大值和最小值，然后子节点中依靠链表遍历范围数据） #### **B-Tree和B+Tree该如何选择？** B-Tree因为非叶子结点也保存具体数据，所以在查找某个关键字的时候找到即可返回。而B+Tree所有的数据都在叶子结点，每次查找都得到叶子结点。所以在同样高度的B-Tree和B+Tree中，B-Tree查找某个关键字的效率更高。 由于B+Tree所有的数据都在叶子结点，并且结点之间有指针连接，在找大于某个关键字或者小于某个关键字的数据的时候，B+Tree只需要找到该关键字然后沿着链表遍历就可以了，而B-Tree还需要遍历该关键字结点的根结点去搜索。 由于B-Tree的每个结点（这里的结点可以理解为一个数据页）都存储主键+实际数据，而B+Tree非叶子结点只存储关键字信息，而每个页的大小有限是有限的，所以同一页能存储的B-Tree的数据会比B+Tree存储的更少。这样同样总量的数据，B-Tree的深度会更大，增大查询时的磁盘I/O次数，进而影响查询效率。