B树

一个m阶的B树,或者空树:

  1. 树中每个节点至多m颗子树，也同时最多由m-1个关键字
  2. 如果根节点不是叶结点,那至少有两个子树
  3. 除根节点以外,所有非叶节点至少有【(m/2)向上取整】个子树
  4. 所有非终端结点都是如下结构（n，point1，key1，point2，key2….）
    1. n代表当前节点的key个数
    2. ponit0指向子树根节点的指针，且point1所指向的子树的所有节点都小于key1
    3. point2子树所有节点大与k1
  5. 所有叶子节点都在一个层次上，并且不带信息，可以看作外部节点或者是查找失败的节点，实际上这些节点并不存在
  • 主要用于做文件的索引，涉及内外存的存取

查找

查找是两个操作：

  1. 在B-树中找节点
  2. 在节点中找关键字

由于B-树存储在磁盘上，则查找1在磁盘上进行的，在磁盘找到节点以后，再将这个节点读入内存进行分析在节点中找关键字。

  • 在磁盘上查找的次数就是待查关键字在B树中的层次树，是决定效率的首要因素。

B+树

一个m阶B+树和m阶B树的差异：

  1. 有n棵子树的节点，含有n个关键字
  2. 所有的叶子节点包含全部关键字的信息，以及含有这个关键字记录的指针，且叶子节点本身所依关键字的大小自小而大顺序链接。
  3. 所有非终端节点可以看作索引，节点中仅含有其子树中的最大或最小的关键字

B/B 树 - 图1

查找

即使在非叶子节点找到了要查找的关键字，也不停止，继续向下查找直到叶子节点

为什么 Mysql 使用B+树

  1. Mysql 是一种关系型数据库，区间访问是常见的一种情况
  • B-树并不支持区间访问（可参见上图）
    • B-树每个节点 key 和 data 在一起，则无法区间查找。
    • B/B 树 - 图2
  • B+树由于数据全部存储在叶子节点，并且通过指针**串**在一起，这样就很容易的进行区间遍历甚至全部遍历。

  1. 见B/B+树的区别第二点：

    B+树叶节点两两相连可大大增加区间访问性，可使用在范围查询等，而B-树每个节点 key 和 data 在一起，则无法区间查找。 B+树的查询效率更加稳定，数据全部存储在叶子节点，查询时间复杂度固定为 > O(log n)。

  2. 最后第三点：

    B+树更适合外部存储。由于内节点无 data 域（于是有更多的空间存放指针），每个节点能索引的范围更大更精确