介绍

B树是为硬盘快速读取数据（降低IO操作次树）而设计的一种平衡的多路查找树。

目前大多数据库及文件索引，都是使用B树或变形来存储实现。

目录

1：为什么B树效率高

2：B树存储

3：B树缺点

一：为什么B树效率高

在大规模数据存储操作中，由于无法一次性加载到内存里。所以避免不了发生内外存交换。所以次数越少，效率表现也越高。

我们来看下面这张图：

这是个典型的b树结构，初始因子为1000。高度仅为3的b树，就可以存储1002001000的数据了。

假设我们要查询最后一个数据:

1: 从硬盘加载根节点搜索。  IO一次

2：根据根节点的指针信息，去加载第二层的节点。 IO一次

3：重复2。  IO一次

我们发现IO只用了3次，就查询了我们要的数据。所以说B树效率很高。

补充：  B树的节点，在硬盘里表现为：柱面里的页(page)或盘块(block) 。如果把索引持久化到内存，只需要一次就够了。

          B树的高效基础：数据已排序。

二：B树结构

  先来张经典的图：

这里是B树存储在硬盘的结构图。

 补充：根节点中17，35在称为关键字(key) ，实际中往往附带更多复杂类型数据。

再来段枯燥的定义：

    1：每个非根节点至少有t-1个关键字，非根内节点至少有t个子女。 t称为度数(degree)，t>=2  。

 .   2：每个节点至多有2t-1关键字，每个内节点最多有2t个子女。

     3：每个叶节点具有相同的深度，即树的高度h 。   

实现

搜索：从根节点搜索，找到返回。找不到递归下级节点，直到叶子节点，找到返回，找不到不存在。

插入：根节点插入，节点满进行分裂，再满递归分裂。 不满直接插入。

删除：查询到节点，删除。不满足定义合并。

更新：查询到子节点，更新数据。

三：B树缺点

从上面的得知，在查询单条数据是非常快的。但如果范围查的话，b树每次都要从根节点查询一遍。

所以在实际应用中，往往采用b树的变形，b+树来存储，只有叶子节点存储数据，每个叶子节点都指向下一个。

主要参考资源

1：算法导论

算法数据结构(一)-B树