B树和B+树

[TOC]

参考：B树、B+树详解

前言

B+ 树是一种存储构造，罕用在数据库建设索引。

筹备常识

m阶的树：树最大分叉有m个，即子节点数最大为m个；

根节点：没有父节点的节点；

叶节点：没有子节点的节点；

外部节点：不是根、叶节点的节点；

二叉搜寻树：左子树中的值要比根节点值 小，右子树中的值要比根节点值 大；

均衡二叉树：二叉搜寻树的非凡状况，左右子树高度一样；

一、B树

B数是均衡多叉树，一个m阶的B树，有如下个性：

  1. 外部节点起码得有ceil(m/2)个子节点；
  2. 根节点不是叶节点时，至多得有2个子节点，即2阶；
  3. m阶的节点中蕴含m-1个数据；
  4. 所有叶子节点高度一致；

二、B+树

B+树是B树变体，对其规定做了些扭转。扭转如下：

  1. 叶子结点由一个有序数组和指向其左边一个叶子结点的指针组成；

  2. 非叶子节点由一个有序数组组成，然而数组元素由一个索引值一个指针组成；

    1. 指针：指向一个叶子节点；
    2. 索引值：指向的那个叶子节点中最小的索引值；
  3. 非叶节点，是工具节点，用于疾速找到指定叶节点，只有叶节点才存储真正的数据（一行数据）；
  4. 叶子节点们相似一个有序链表;
  5. m阶的节点中蕴含m个数据;

2.1 为什么B+树适宜数据库？

  1. B+树便于范畴查问，这是最次要的。

只须要查找最右边范畴即可，查到后遍历往右遍历叶子结点，晓得碰到左边范畴完结，这样就筛出了所有范畴内数据。

B树的范畴查找用的是中序遍历，而B+树用的是在链表上遍历；

  1. B+树的磁盘读写代价更低。

B+树的外部结点并没有指向关键字具体信息的指针。因而其外部结点绝对B 树更小。如果把所有同一外部结点的关键字寄存在同一盘块中，那么盘块所能包容的关键字数量也越多。一次性读入内存中的须要查找的关键字也就越多。相对来说IO读写次数也就升高了；

  1. B+树查问效率更加稳固

因为非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查问的门路长度雷同，导致每一个数据的查问效率相当；