二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。
是数据结构中的一类。在一般情况下，查询效率比链表结构要高。
由链表演变而来, 而二叉查找树则在树中加入了二分查找法的思想。
链表就是特殊化的树, 树就是特殊化的图
一棵空树，或者是具有下列性质的二叉树：
二查查找树如图:
二叉树的遍历方式有：前序遍历(根左右)、中序遍历(左根右)、后序遍历(左右根)。
而又因二叉查找树内节点的值二分的特性，在二叉查找树进行中序遍历时、便可得到顺序升序的一组值
上图经过中序遍历后得到的值为：1 3 4 6 7 8 10 13 14
1970年，R.Bayer和E.mccreight提出了一种适用于外查找的树，它是一种平衡的多叉树，称为B树（或B-树、B_树）。
一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树，或者是满足下列性质的树：
在B-树中，每个结点中关键字从小到大排列，并且当该结点的孩子是非叶子结点时，该k-1个关键字正好是k个孩子包含的关键字的值域的分划。
因为叶子结点不包含关键字，所以可以把叶子结点看成在树里实际上并不存在外部结点，指向这些外部结点的指针为空，叶子结点的数目正好等于树中所包含的关键字总个数加1。
B-树中的一个包含n个关键字，n+1个指针的结点的一般形式为： （n,P0,K1,P1,K2,P2,…,Kn,Pn）
其中，Ki为关键字，K1<K2<…<Kn, Pi 是指向包括Ki到Ki+1之间的关键字的子树的指针。
如图:
在B-树中查找给定关键字的方法是，首先把根结点取来，
在根结点所包含的关键字K1,…,Kn查找给定的关键字（可用顺序查找或二分查找法），
若找到等于给定值的关键字，则查找成功；
否则，一定可以确定要查找的关键字在Ki与Ki+1之间，Pi为指向子树根节点的指针，
此时取指针Pi所指的结点继续查找，直至找到，或指针Pi为空时查找失败。
B+树是一种树数据结构，通常用于数据库和操作系统的文件系统中。
B+树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。
B+树元素自底向上插入，这与二叉树恰好相反。
B+树在节点访问时间远远超过节点内部访问时间的时候，比可作为替代的实现有着实在的优势。
这通常在多数节点在次级存储比如硬盘中的时候出现。
通过最大化在每个内部节点内的子节点的数目减少树的高度，平衡操作不经常发生，而且效率增加了。
这种价值得以确立通常需要每个节点在次级存储中占据完整的磁盘块或近似的大小。
B+背后的想法是内部节点可以有在预定范围内的可变数目的子节点。
因此，B+树不需要象其他自平衡二叉查找树那样经常的重新平衡。对于特定的实现在子节点数目上的低和高边界是固定的。
B+ 树的创造者Rudolf Bayer没有解释B代表什么。最常见的观点是B代表平衡(balanced)，因为所有的叶子节点在树中都在相同的级别上。
在 B+ 树中的节点通常被表示为一组有序的元素和子指针。如果此B+树的序数（order）是m ，
则除了根之外的每个节点都包含最少 个元素最多 m-1 个元素，对于任意的节点有最多 m 个子指针。
对于所有内部节点，子指针的数目总是比元素的数目多一个。
因为所有叶子都在相同的高度上，节点通常不包含确定它们是叶子还是内部节点的方式。
每个内部节点的元素充当分开它的子树的分离值。
例如，如果内部节点有三个子节点（或子树）则它必须有两个分离值或元素a1和a2。
在最左子树中所有的值都小于等于a1，在中间子树中所有的值都在a1和a2之间((a1，a2]），而在最右子树中所有的值都大于a2。
B+树是B树的一种变形，比B树具有更广泛的应用，m阶 B+树有如下特征:
我们在美团外卖下单, 加入没有立即支付, 进入订单详情页面, 会显示倒计时, 如果倒计时完毕, 订单就会被自动取消
这篇文章, 笔者想深入剖析订单超时自动取消的业务场景
我们自然而然的想到, 通过一个定时器, 定时查询最近未支付的订单
遍历查询出来的订单, 对其进行取消操作
这种方案实现相对简单, 但间隔的查询, 会对数据库造成一定的IO压力
特别是在订单量非常高时, 高频次的查询对数据库的性能是个不小的考验
我们可以使用 Timer, ScheduledExecutorService, Quartz 来实现定时任务
然而, 假设应用A通过Quartz调度三个定时任务A,B,C
当集群部署时, 可能出现多台机器同时执行任务的风险
虽然抢占任务, 我们可以通过Redis建立分布式锁, 但是这种方式并不优雅
同时定时任务应用内调度层经常空跑, 我们预期是希望三个定时任务A,B,C能均匀分布运行在应用A的不同实例内
