上一期我们谈到了数据库实现快速查找的所使用的的HASH算法，能够实现O(1)复杂的快速查找，HASH算法虽然好，但是有一个致命的缺点，就是HASH函数算出的散列值，通常是随机分布，没有顺序性。而很多时候数据库的数据是有数值含义的，需要实现诸如
SELECT * FROM CUSTOMER WHERE ORDER_AMOUT > 100
类似这样的范围查找，这样的需求，哈希算法是无法实现，那我们就需要有一类能够保持关键字段稳定排列的算法或数据结构，这时候我们就需要用到BTREE，B树
B树
1970年，R.Bayer和E.mccreight提出了一种适用于外查找的树，它是一种平衡的多叉树，称为B树（或B-树、B_树）。
一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树，或者是满足下列性质的树：
1、根结点至少有两个子女；
2、每个非根节点所包含的关键字个数 j 满足：【m/2】 - 1 <= j <= m - 1；
3、除根结点以外的所有结点（不包括叶子结点）的度数正好是关键字总数加1，故内部子树个数 k 满足：【m/2】 <= k <= m ；
4、所有的叶子结点都位于同一层。
B树的查找
如图所示，B+树中含有两个头指针，一个指向整棵树的根结点，另一个指向关键字最小的叶子结点。同时所有的叶子结点依据其关键字的大小自小而大顺序链接，所有的叶子结点构成了一个 sqt 指针为头指针的链表。
所以，B+树可以进行两种查找运算：一种是利用 sqt 链表做顺序查找，另一种是从树的根结点开始，进行类似于二分查找的查找方式。
能够使用二分法进行查找，就意味着查找效率接近O(lgN)级别，可以以非常快的速度在大量的数据中进行查找，并且也满足了我们一开始想要实现的还能够进行顺序查找的操作。
B树在数据库中的使用
B树在数据库中的使用有
B树索引：为了加快查找速度，我们可以在数据记录的关键字段上建立B树索引，这样的索引既可以进行等值查找，也可以进行范围查找，等值查找的操作速度略逊于HASH
聚集表/索引组织表：为了能够实现数据的快速访问，很多数据库甚至将表按照住建组织成了B树的形式，这样按照主键来查询数据或者范围查找数据是非常快的，比如MySQL InnoDB引擎的表的组织形式就是B树
