这次我们要发布一个关于B-Tree的合集。第一部分首先介绍B树的基本概念。B树不同于bst等二叉树。B树是多叉树，B树是自平衡树。B树的Search、Insert、Remove算法的时间复杂度为O(logN)。B树经常用于数据库中。数据库往往数据量非常大，不可能存储在内存中，需要存储在硬盘中。硬盘是块设备，一次读取一个区域，而B树是多叉树，所以有多个key，所以一个区域可以包含多个key。另外，硬盘比内存慢，B树比二叉树短，因为它是多叉树，所以更能减少硬盘交互次数。B-tree有一些属性，我更喜欢称之为规约或者规约的结果：1.B-tree用来衡量每个节点（node）大小的度量称为度（degree，缩写作为t)和Rank(顺序，缩写为m)。度和位是两个不同的角度。度是指B树的任意节点（根节点除外）至少有t个分叉（最多2t个分叉），秩是指B树的任意节点（根节点除外）有at大多数m叉子。后面会用度来解释B-tree。2.因为任何节点（根节点除外）至少有t个分叉，所以任何节点（根节点除外）至少有t-1个密钥。3、同2，任何节点（根节点除外）最多有2t-1个key。可见是奇数。4.任意一个节点中的key按照升序排列。因此可以方便地在节点上使用二分查找。5.任意两个键k1和k2之间的子树的键都在k1到k2的范围内。如上图所示。6.插入只会发生在叶节点上。7、B树的Search、Insert、Remove都是从根节点开始的。8.所有叶子节点都在同一层级。9.和其他自平衡树一样，B树的Search、Insert、Remove算法的时间复杂度都是O(logN)。
