一.B树介绍

（一）.B树存在意义

（二）.B树的规则

二.B树实现原理及代码

（一）.实现原理

（二）.代码

三.B+树

（一）.概念

（二）.应用

①MyISAM

②InnoDB

四.B*树

一.B树介绍

（一）.B树存在意义

B树主要用于磁盘文件的检索操作。众所周知，平衡二叉树（AVL树、红黑树）搜索的时间复杂度是O(log^n)。虽然很快，但如果数据在磁盘中且有上亿量级的数据，即便只有30次左右的IO操作，速度也是非常慢的。因为磁盘IO速度极慢，主要是寻道操作影响，平均8ms左右。

因此，磁盘数据的检索不适合使用平衡二叉树，B树正式上线。

B树可以看成是压缩版的平衡二叉树，每一个节点上都有保存有多个值，且有多个叶子节点。

一般而言，B树的检索次数在个位量级，这取决于每个节点上能保存多少个值。

上亿量级的数据，红黑树可能需要30次左右，但B树只需要3-4次即可。

（二）.B树的规则

1. 根节点至少有两个孩子，规定每个节点最多存m - 1个元素

2. 每个分支有k - 1个元素和k个孩子节点，其中 ceil(m/2) ≤ k ≤ m，ceil是向上取整函数。

即孩子节点个数 = 元素个数 + 1（必须是分支节点）

3. 每个叶子节点都包含k-1个元素，其中 ceil(m/2) ≤ k ≤ m

4. 所有的叶子节点都在同一层

5. 每个节点中的元素从小到大排列

二.B树实现原理及代码

（一）.实现原理

以插入3、6、4、2、7、1、5为例，假定m为3，即每个节点最多存2个元素

首先，B树的节点图示如下：

这里多开辟一个空间是为了当元素数量满3时便于之后分裂。

依次插入，注意插入后元素要按从小到大排列（直接插入排序）：

此时，元素数量已经满3，要进行分裂操作。

分裂：节点对半分裂，将4提出作为父节点（根节点），3和6叶子节点分别作为4的左右孩子节点

之后2与4比较并插入，插入位置均是叶子节点（所有插入的元素都是这样）。

2小于4，因此插入左叶子节点，之后与3比较，小于3，插入左边。

7大于4因此插入右叶子节点，大于6，插入6右边

插入1后，此时右叶子节点满3了，要进行分裂：

分裂方式一样，将2提至父节点，1和3对半分。

2比4小，将4后移，同时4的右子树后移，1作为2的左子树，3作为2的右子树。

5插入后，4的右子树满3，进行分裂：

此时根节点满3，也要分裂：

将4提出作为根节点，2和6对半分，各自的叶子节点也对半分。

以上步骤包括所有B树插入的可能情况。

（二）.代码

// - - -    : _key
//- - - -   : _child
template<class T, size_t M>
struct BTreeNode {size_t _n;//已有值数量T _key[M + 1];//存放值,多一个位置，便于满时添加BTreeNode* _child[M + 1];//存放子节点们地址BTreeNode* _parent;//父节点BTreeNode()//初始化 + 默认构造:_n(0),_parent(nullptr){for (size_t i = 0; i <= M; i++) {_key[i] = T();_child[i] = nullptr;}}
};template<class T, size_t M>
class BTree {typedef BTreeNode<T, M> Node;void _insertKey(Node* cur, const T& key, Node* child)//child:右孩子{int i = cur->_n - 1;for (; i >= 0; i--)//这里不需要再判断key是否已有，insert中已经判断{if (key < cur->_key[i])//数据后移{cur->_key[i + 1] = cur->_key[i];cur->_child[i + 2] = cur->_child[i + 1];}else//key小于当前数据{break;}}//   - - -    _key//   - - - -  _child// ^   ^// i  childcur->_key[i + 1] = key;cur->_child[i + 2] = child;if (child){child->_parent = cur;}cur->_n++;}
public:pair<Node*, int> find(const T& key)//寻找节点{Node* cur = _root;Node* parent = nullptr;while (cur){int i = 0;while (i < cur->_n){if (key > cur->_key[i]){i++;}else if (key < cur->_key[i]){break;}else{return make_pair(cur, i);}}parent = cur;cur = cur->_child[i];}return make_pair(parent, -1);//没有找到}bool insert(const T& key)//插入值{if (_root == nullptr)//插入的是第一个节点{_root = new Node;_root->_key[0] = key;_root->_n++;return true;}//插入的不是第一个节点pair<Node*, int> ret = find(key);//找节点if (ret.second >= 0) return false;//节点已经存在//节点不存在，进行插入操作Node* cur = ret.first;Node* brother = nullptr;T midValue = key;//因为key是const，不能直接使用while (1){_insertKey(cur, midValue, brother);//先插入//判断cur是否已经满了if (cur->_n == M){//满了，分裂brother = new Node;T keyValue = cur->_key[M / 2];cur->_key[M / 2] = T();int i = M / 2 + 1, j = 0;for (; i < M; i++)//分裂{brother->_key[j] = cur->_key[i];brother->_child[j] = cur->_child[i];cur->_key[i] = T();cur->_child[i] = nullptr;if (brother->_child[j]){brother->_child[j]->_parent = brother;}j++;}brother->_n = j;cur->_n = M - brother->_n - 1;//-1是因为还要把向上提到父节点的减去brother->_child[j] = cur->_child[M];//最后一个子节点也需要添加cur->_child[M] = nullptr;if (brother->_child[j]){brother->_child[j]->_parent = brother;}//判断cur是否是根节点，是就需要手动创建节点并链接叶子，因为_insertKey只能同层插入，不能更新_rootif (cur->_parent == nullptr){_root = new Node;_root->_key[0] = keyValue;_root->_child[0] = cur;_root->_child[1] = brother;cur->_parent = _root;brother->_parent = _root;_root->_n = 1;break;}else{midValue = keyValue;cur = cur->_parent;}}else{break;}}return true;}void levelOrder()//层序遍历{queue<Node*> qu;qu.push(_root);while (!qu.empty()){int n = qu.size();while (n--){Node* node = qu.front();qu.pop();int i = 0;for (; i < node->_n; i++){cout << node->_key[i] << " ";if (node->_child[i]){qu.push(node->_child[i]);}}if (node->_child[i]){qu.push(node->_child[i]);}cout << "| ";}cout << endl;}}private:Node* _root = nullptr;
};