目录

1. 常见的搜索结构

2. B树概念

3. B-树的插入分析

4. B-树的插入实现

        4.1 B-树的节点设计

       4.2 插入key的过程

4.4 B-树的简单验证

4.5 B-树的性能分析

4.6 B-树的删除

5. B+树和B*树

5.1 B+树

5.2 B*树

5.3 总结

6. B-树的应用

6.1 索引

6.2 MySQL索引简介

6.2.1 MyISAM

6.2.2 InnoDB

---

1. 常见的搜索结构

 

4.3 B-树的插入实现  

        

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;// M 叉树，即一个节点最多有M个孩子，M-1 个数据域
template <class K, int M = 3>struct BTreeNode
{K _keys[M]; //存放元素BTreeNode<K, M> *_pSub[M + 1];BTreeNode<K, M> *_pParent;size_t _size; //节点元素的个数BTreeNode() : _pParent(NULL), _size(0){for (size_t i = 0; i <= M; i++){_pSub[i] = nullptr;}}bool Insert(const K &key){// 如果树为空，直接插入if (NULL == _pRoot){_pRoot = new Node();_pRoot->_keys[0] = key;_pRoot->_size = 1;return true;}// 找插入位置，如果该元素已经存在，则不插入pair<PNode, int> ret = Find(key);if (-1 != ret.second)return false;K k = key;PNode temp = NULL;PNode pCur = ret.first;while (true){// 将key插入到pCur所指向的节点中_InsertKey(pCur, k, temp);// 检测该节点是否满足B-树的性质，如果满足则插入成功返回，否则，对pCur节点进行分裂if (pCur->_size < M) return true;// 申请新节点temp = new Node;// 找到pCur节点的中间位置// 将中间位置右侧的元素以及孩子搬移到新节点中int mid = (M >> 1);for (size_t i = mid + 1; i < pCur->_size; ++i){temp->_keys[temp->_size] = pCur->_keys[i];temp->_pSub[temp->_size++] = pCur->_pSub[i];// 跟新孩子节点的双亲if (pCur->_pSub[i])pCur->_pSub[i]->_pParent = temp;}// 注意：孩子比关键字多搬移一个temp->_pSub[temp->_size] = pCur->_pSub[pCur->_size];if (pCur->_pSub[pCur->_size])pCur->_pSub[pCur->_size]->_pParent = temp;// 更新pCur节点的剩余数据个数pCur->_size -= (temp->_size + 1);// 如果分裂的节点为根节点，重新申请一个新的根节点，将中间位置数据以及分裂出的新节点插入到新的根节点中，插入结束 if (pCur == _pRoot){_pRoot = new Node;_pRoot->_keys[0] = pCur->_keys[mid];_pRoot->_pSub[0] = pCur;4.4 B - 树的简单验证 对B树进行中序遍历，如果能得到一个有序的序列，说明插入正确。 4.5 B - 树的性能分析 对于一棵节点为N度为M的B - 树，查找和插入需要$log{M - 1} N$ ~$log{M / 2} N$次比较，这个很好证 明：对于度为M的B - 树，每一个节点的子节点个数为M / 2 ~(M - 1) 之间，因此树的高度应该在要 $log{M - 1} N$和$log{M / 2} N$之间，在定位到该节点后，再采用二分查找的方式可以很快的定位 到该元素。 B - 树的效率是很高的，对于N = 62 * 1000000000个节点，如果度M为1024，则 $log_{M / 2} N$ <=4，即在620亿个元素中，如果这棵树的度为1024，则需要小于4次即可定位到该节点，然后利用 二分查找可以快速定位到该元素，大大减少了读取磁盘的次数。 4.6 B - 树的删除 学习B树的插入足够帮助我们理解B树的特性了，如果对删除有兴趣的同学们参考《算法导论》--伪代码和《数据结构 - 殷人昆》--C++ 实现代码。 5. B + 树和B * 树 5.1 B + 树 B + 树是B树的变形，是在B树基础上优化的多路平衡搜索树，B + 树的规则跟B树基本类似，但是又 在B树的基础上做了以下几点改进优化： _pRoot->_pSub[1] = temp;_pRoot->_size = 1;pCur->_pParent = temp->_pParent = _pRoot;return true;}else{// 如果分裂的节点不是根节点，将中间位置数据以及新分裂出的节点继续向pCur的双亲中进行插入k = pCur->_keys[mid];pCur = pCur->_pParent;}}return true;}
};int main()
{system("pause");return 0;
}

4.4 B-树的简单验证