html5 网站开发 适配,wordpress设置用户访问个数据库,建立官网需要多少钱,网站专题制作流程B树、B树、B*树 1. 常见的搜索结构2. B树概念3. B树的插入分析4. B树的插入实现4.1 B树的节点设计4.2 B树的部分插入实现14.3 B树的查找4.4 B树的部分插入实现24.5 插入key的过程4.7 B树的插入完整代码4.8 B树的简单验证4.9 B树的删除4.10 B树的性能分析 5. B树6. B*树7. 总结8… B树、B树、B*树 1. 常见的搜索结构2. B树概念3. B树的插入分析4. B树的插入实现4.1 B树的节点设计4.2 B树的部分插入实现14.3 B树的查找4.4 B树的部分插入实现24.5 插入key的过程4.7 B树的插入完整代码4.8 B树的简单验证4.9 B树的删除4.10 B树的性能分析 5. B树6. B*树7. 总结8. B树的应用8.1 索引8.2 MySQL索引简介8.2.1 MyISAM8.2.2 InnoDB 点赞收藏关注 你的支持是对我最大的鼓励我们一起努力吧! 1. 常见的搜索结构
内查找
种类数据格式时间复杂度顺序查找无要求O(N)二分查找有序O(logN)二叉搜索树无要求O(N)二叉平衡树(AVL树和红黑树)无要求O(logN)哈希无要求O(1)
外查找 B树系列
以上结构适合用于数据量相对不是很大能够一次性存放在内存中进行数据查找的场景。如果数据量很大比如有100G数据无法一次放进内存中那就只能放在磁盘上了如果放在磁盘上有需要搜索某些数据那么如何处理呢那么我们可以考虑将存放关键字及其映射的数据的地址放到一个内存中的搜索树的节点中找数据时比较关键字找到关键字也就找到这个数据在磁盘的地址然后去这个地址去磁盘访问数据。
但是这样还有一些问题如果关键字不是整型而是字符串数据量大了在内存中这棵树存可能存不下。那怎么办 节点可以不存关键字 只存对应磁盘的地址。这个时候查找就要拿着地址去访问磁盘然后看关键字是否匹配。这个时候还是一样关键字比当前节点关键字大往右走否则往左走。每一次比较节点都是一次IO。
但是这里的问题是要走高度次磁盘IO因为节点里面只有地址要进行关键字比较就要读一次磁盘。这个时候 AVL/红黑树 就不适合了都是O(logN)虽然在内存中查找比较快10亿个数字需要30次。但是在磁盘中如果是30次IO那就很慢了。还有哈希表虽然查找说是O(1)但是这个O(1)并不是一次而是常数次更大的问题是极端场景下哈希冲突可能会非常严重效率会下降很多。即使哈希表挂的是红黑树还是O(logN)。 使用平衡二叉树搜索树的缺陷
平衡二叉树搜索树的高度是logN这个查找次数在内存中是很快的。但是当数据都在磁盘中时访问磁盘速度很慢在数据量很大时logN次的磁盘访问是一个难以接受的结果。
使用哈希表的缺陷
哈希表的效率很高是O(1)但是一些极端场景下某个位置冲突很多导致访问次数剧增也是难以接受的。
那有没有更好的数据结构能够替代上面的东西呢 B树系列
平衡搜索树基础上找优化空间
B树的思路是这样的之前AVL/红黑树 存10亿个数据大概需要30层能不能把高度压缩一下从30层压缩到几层。如何压呢很简单是不是让单层存更多是不是进行压缩了。如何让单层存更多呢
压缩高度二叉变多叉
注意到一个节点就一个地址一个地址对应一行数据那数据多了地址也很多。地址很多内存也是有限的怎么办
一个节点存有多个关键字及映射的值
2. B树概念
1970年R.Bayer和E.mccreight提出了一种适合外查找的树它是一种平衡的多叉树称为B树(后面有一个B的改进版本B树然后有些地方的B树写的的是B-树注意不要误读成B减树)。一棵m阶(m2)的B树是一棵平衡的M路平衡搜索树可以是空树或者满足一下性质
根节点至少有两个孩子每个分支节点都包含k-1个关键字和k个孩子其中 ceil(m/2) ≤ k ≤ m ceil是向上取整函数分支节点孩子比关键字保持多一个的关系每个叶子节点都包含k-1个关键字其中 ceil(m/2) ≤ k ≤ m所有的叶子节点都在同一层每个节点中的关键字从小到大排列节点当中k-1个元素正好是k个孩子包含的元素的值域划分每个结点的结构为nA0K1A1K2A2… KnAn 其中Ki(1≤i≤n)为关键字且KiKi1(1≤i≤n-1)。Ai(0≤i≤n)为指向子树根结点的指针。且Ai所指子树所有结点中的关键字均小于Ki1。n为结点中关键字的个数满足ceil(m/2)-1≤n≤m-1。
Ai是指向孩子的指针Ki是关键字从每个结点的结构上我们就可以看到孩子的数量比关键字多一个。
总结 实际上M通常会设计的比较大M 1024一个节点1023个关键字1024个孩子。
为什么B树规则这么复杂这都是它的插入有关。
3. B树的插入分析
为了简单起见假设M 3. 即三叉树正常来说每个节点中最多存储两个关键字最少一个关键字两个关键字可以将区间分割成三个部分因此节点应该有三个孩子。
用序列{53, 139, 75, 49, 145, 36, 101}构建B树的过程如下
根节点至少有两个孩子这里可以这样理解最开始插入一个关键字它有两个孩子可以认为是空。所以根节点要单独拿出来。
注意到 M 3正常来说不应该是2个关键字和3个孩子吗为什么这里是3个关键字和4个孩子多放一个是有原因的。
插入139没有什么影响 在插75如果不多开一个这个地方待会实现会变得复杂。插入的值因为要保证是有序的所以可能在最前面可能在中间可能在最后面。但是现在并不敢就直接插入一插入就要越界了。关键字个数等于M关键字最多只能有M-1个。 基于这里的原因我们就多给一个。 多给一个空间的好处是方便插入直接插入满了在分裂不用管插在哪要挪动那些数据也不怕越界。浪费一个空间不算啥。 关键字的数量等于M则满了满了就分裂出一个兄弟提取中位数M/2将中位数右边值和孩子拷贝给兄弟。将中位数给父亲如果没有父亲就创建新的根。 插入49注意新增节点只能在叶子节点插入。要保证节点内关键字是有序的内部可以用直接插入排序挪动关键字和孩子。 插入145 插入36发现关键字个数等于M申请一个兄弟找到中位数将中位数右边的关键字和孩子分裂拷贝兄弟提取中位数插入到父亲。插入要移动关键字和它的右孩子。 插入之后别忘记最后要连接兄弟节点。 插入101关键字等于M会分裂拷贝给兄弟然后提取中位数给父亲父亲插入之后父亲的关键字也等于M了也会分裂。分裂拷贝找到中位数M/2申请兄弟节点将中位数右边的关键字以及左孩子拷贝给兄弟最后还要在将最后一个孩子也要拷贝给兄弟。然后提取中位数给父亲父亲插入之后如果父亲不满就结束如果满就持续分裂。 B树的插入你会发现它是天然平衡因为它是向右和向上生长。
新插入的节点一定是在叶子节点。因为叶子节点没有孩子不影响关键字和孩子的关系。分支节点孩子保持比关键字多一个的关系。叶子节点满了分裂出一个兄弟提取中位数向父亲插入一个值和孩子。
根节点分裂增加一层。 越到最后根节点越不容易分裂。
假设 M 1024。一个节点最多放1023个关键字1024个孩子。
4层M路B树就可以放一万亿个关键字和孩子了。 当然这是满的情况不满我们也可以看一下然后对比。 插入过程总结
如果树为空直接插入新节点中该节点为树的根节点树非空找待插入元素在树中的插入位置(注意找到的插入节点位置一定在叶子节点中)检测是否找到插入位置(假设树中的key唯一即该元素已经存在时则不插入)按照插入排序的思想将该元素插入到找到的节点中检测该节点是否满足B-树的性质即该节点中的元素个数是否等于M如果小于则满足如果插入后节点不满足B树的性质需要对该节点进行分裂 申请新节点 找到该节点的中间位置 将该节点中间位置右侧的元素以及其孩子搬移到新节点中 将中间位置元素以及新节点往该节点的双亲节点中插入即继续4如果向上已经分裂到根节点的位置插入结束
4. B树的插入实现
4.1 B树的节点设计
目前B树节点还差一个东西等下面用到了在补充。
templateclass K,size_t M
struct BTreeNode
{//K _keys[M - 1];//BTreeNodeK, M* _subs[M];// M叉树即一个节点最多有M-1个关键字,M个孩子// 为了方便插入以后再分裂多给一个空间K _keys[M];BTreeNodeK, M* _subs[M 1];size_t _n;//记录实际存储多少个关键字BTreeNode(){for (size_t i 0; i M; i){_keys[i] K();_subs[i] nullptr;}_subs[M] nullptr;_n 0;}
};4.2 B树的部分插入实现1
//数据是存在磁盘K是磁盘地址
templateclass K,size_t M
class BTree
{typedef BTreeNodeK, M Node;
public:bool Insert(const K key){// 如果树为空直接插入if (_root nullptr){_root new Node;_root-_keys[0] key;_root-_n 1;return true;}// 找插入位置如果该元素已经存在则不插入auto ret Find(key);}private:Node* _root nullptr;
};下面先实现B树的查找
4.3 B树的查找
比当前关键字小一定在它的左边比它大就往右继续找如果越界了就往最后一个关键字的右孩子去找。走到叶子节点的nullptr说明没找到。
左孩子下标与关键字下标相等。 右孩子下标比关键字下标大1。 // 返回值: Node代表找到的节点,int为该元素在该节点中的位置
pairNode*, int Find(const K key)
{// 从根节点的位置开始查找Node* cur _root;while (cur)// 节点存在{// 在一个节点查找size_t i 0;while (i cur-_n){if (key cur-_key[i])// 该元素可能在i的左边的孩子节点中{break;}else if (key cur-_keys[i])// 继续向右查找,越界后往最后一个关键字的右孩子去找{i;}else{return make_pair(cur, i);// 找到返回}}//往孩子去跳cur cur-_subs[i];}//没找到return make_pair(nullptr, -1);
}找到在中间就会返回了没找到正常返回nullptr和-1但是因为插入如果find没有找到我们期望把叶子节点返回来前面说了新插的一定在叶子节点。所以我们期望find在没找到的时候顺便把叶子节点给我返回来。
// 返回值: Node代表找到的节点,int为该元素在该节点中的位置
pairNode*, int Find(const K key)
{// 从根节点的位置开始查找Node* cur _root;Node* parent nullptr;while (cur)// 节点存在{// 在一个节点查找size_t i 0;while (i cur-_n){if (key cur-_keys[i])// 该元素可能在i的左边的孩子节点中{break;}else if (key cur-_keys[i])// 继续向右查找,越界后往最后一个关键字的右孩子去找{i;}else{return make_pair(cur, i);// 找到返回}}//往孩子去跳parent cur;cur cur-_subs[i];}//没找到,把叶子节点返回去return make_pair(parent, -1);
}4.4 B树的部分插入实现2
void InsertKey(Node* node, const K key)
{}bool Insert(const K key)
{// 如果树为空直接插入if (_root nullptr){_root new Node;_root-_keys[0] key;_root-_n 1;return true;}// 找插入位置如果key已经存在则不插入auto ret Find(key);if (ret.second 0){return false;}// 如果没有找到Find顺便带回了要插入的那个叶子节点Node* cur ret.first;//插入InsertKey(cur,key);// 满了就要分裂// 没有满插入就结束if (cur-_n M){return true;}else{//分裂size_t mid M / 2;// 申请兄弟节点,分裂一半给兄弟 [mid 1, M - 1]Node* brother new Node;size_t j 0;size_t i mid 1;for (; i M; i){// 分裂拷贝key和key的左孩子给兄弟 (分裂的是叶子节点没有孩子,分支节点和根节点都有孩子)brother-_keys[j] cur-_keys[i];brother-_subs[j] cur-_subs[i];j;// 拷走重置一下方便观察cur-_keys[i] K();cur-_subs[i] nullptr;}//最后一个右孩子也要拷贝给兄弟brother-_subs[j] cur-_subs[i];cur-_subs[i] nullptr;//更新节点关键字个数brother-_n j;cur-_n - (brother-_n 1); // 1表示中位数要提取给父亲//提取中位数给父亲K nemid cur-_keys[mid];cur-_keys[mid] K();//分裂后向父亲插入}分裂后向父亲插入有两种情况
本身是根没有父亲叶子节点或者分支节点有父亲
一个有父亲一个没父亲这两种情况该如何区分呢
很好解决我们给节点增加一个父指针
templateclass K,size_t M
struct BTreeNode
{//K _keys[M - 1];//BTreeNodeK, M* _subs[M];// M叉树即一个节点最多有M-1个关键字,M个孩子// 为了方便插入以后再分裂多给一个空间K _keys[M];BTreeNodeK, M* _subs[M 1];size_t _n;//记录实际存储多少个关键字BTreeNodeK, M* _parent;//父指针BTreeNode(){for (size_t i 0; i M; i){_keys[i] K();_subs[i] nullptr;}_subs[M] nullptr;_parent nullptr;_n 0;}
};因为节点增加了父指针所以我们先把现有的插入代码修改一下
bool Insert(const K key)
{// 如果树为空直接插入if (_root nullptr){_root new Node;_root-_keys[0] key;_root-_n 1;return true;}// 找插入位置如果key已经存在则不插入auto ret Find(key);if (ret.second 0){return false;}// 如果没有找到Find顺便带回了要插入的那个叶子节点Node* cur ret.first;InsertKey(cur,key);// 满了就要分裂// 没有满插入就结束if (cur-_n M){return true;}else{size_t mid M / 2;// 申请兄弟节点,分裂一半给兄弟 [mid 1, M - 1]Node* brother new Node;size_t j 0;size_t i mid 1;for (; i M; i){// 分裂拷贝key和key的左孩子给兄弟 (分裂的是叶子节点没有孩子,分支节点和根节点都有孩子)brother-_keys[j] cur-_keys[i];brother-_subs[j] cur-_subs[i];// 如果孩子存在,分裂孩子给兄弟之后,孩子的父指针指向兄弟if (cur-_subs[i]){cur-_subs[i]-_parent brother;}j;// 拷走重置一下方便观察cur-_keys[i] K();cur-_subs[i] nullptr;}//最后一个右孩子也要拷贝给兄弟brother-_subs[j] cur-_subs[i];//孩子的父指针指向兄弟if (cur-_subs[i])cur-_subs[i]-_parent brother;cur-_subs[i] nullptr;//更新节点关键字个数brother-_n j;cur-_n - (brother-_n 1); // 1表示中位数要提取给父亲//提取中位数给父亲K nemid cur-_keys[mid];cur-_keys[mid] K();}}如果本身是根没有父亲很简单创建一个根然后插入一个关键字和两个孩子cur和brother。
bool Insert(const K key)
{// 如果树为空直接插入if (_root nullptr){_root new Node;_root-_keys[0] key;_root-_n 1;return true;}// 找插入位置如果key已经存在则不插入auto ret Find(key);if (ret.second 0){return false;}// 如果没有找到Find顺便带回了要插入的那个叶子节点Node* cur ret.first;InsertKey(cur,key);// 满了就要分裂// 没有满插入就结束if (cur-_n M){return true;}else{size_t mid M / 2;// 申请兄弟节点,分裂一半给兄弟 [mid 1, M - 1]Node* brother new Node;size_t j 0;size_t i mid 1;for (; i M; i){// 分裂拷贝key和key的左孩子给兄弟 (分裂的是叶子节点没有孩子,分支节点和根节点都有孩子)brother-_keys[j] cur-_keys[i];brother-_subs[j] cur-_subs[i];// 如果孩子存在,分裂孩子给兄弟之后,孩子的父指针指向兄弟if (cur-_subs[i]){cur-_subs[i]-_parent brother;}j;// 拷走重置一下方便观察cur-_keys[i] K();cur-_subs[i] nullptr;}//最后一个右孩子也要拷贝给兄弟brother-_subs[j] cur-_subs[i];//孩子的父指针指向兄弟if (cur-_subs[i])cur-_subs[i]-_parent brother;cur-_subs[i] nullptr;//更新节点关键字个数brother-_n j;cur-_n - (brother-_n 1); // 1表示中位数要提取给父亲//提取中位数给父亲K nemid cur-_keys[mid];cur-_keys[mid] K();// 分裂的是根节点没有父亲if (cur-_parent nullptr){_root new Node;_root-_keys[0] nemid;_root-_subs[0] cur;_root-_subs[1] brother;_root-_n 1;cur-_parent _root;brother-_parent _root;return true;}else // 分裂的是叶子节点或者是分支节点有父亲{// 转换成往cur-parent 去插入cur-[mid] 和 brother}}}如果分裂的是叶子节点或者是分支节点有父亲转化为向父亲节点插入关键字和兄弟。 注意我们刚才写了一个InsertKey插入函数参数只有key没有孩子的参数为了让分裂后插入也可以使用这个函数因此我们可以增加一个孩子的参数。如果是向叶子节点插入关键字我们可以认为它的孩子为nullptr。这样不管是向叶子节点插入还是分裂后向父亲插入中位数和兄弟InsetKey这个函数都可以用。并且插入应该是一个循环。 bool Insert(const K key)
{// 如果树为空直接插入if (_root nullptr){_root new Node;_root-_keys[0] key;_root-_n 1;return true;}// 找插入位置如果key已经存在则不插入auto ret Find(key);if (ret.second 0){return false;}// 如果没有找到Find顺便带回了要插入的那个叶子节点// 循环每次往cur插入 newkey和childNode* cur ret.first;Node* child nullptr;K newkey key;while (1){InsertKey(cur, newkey, child);// 满了就要分裂// 没有满插入就结束if (cur-_n M){return true;}else{size_t mid M / 2;// 申请兄弟节点,分裂一半给兄弟 [mid 1, M - 1]Node* brother new Node;size_t j 0;size_t i mid 1;for (; i M; i){// 分裂拷贝key和key的左孩子给兄弟 (分裂的是叶子节点没有孩子,分支节点和根节点都有孩子)brother-_keys[j] cur-_keys[i];brother-_subs[j] cur-_subs[i];// 如果孩子存在,分裂孩子给兄弟之后,孩子的父指针指向兄弟if (cur-_subs[i]){cur-_subs[i]-_parent brother;}j;// 拷走重置一下方便观察cur-_keys[i] K();cur-_subs[i] nullptr;}//最后一个右孩子也要拷贝给兄弟brother-_subs[j] cur-_subs[i];//孩子的父指针指向兄弟if (cur-_subs[i])cur-_subs[i]-_parent brother;cur-_subs[i] nullptr;//更新节点关键字个数brother-_n j;cur-_n - (brother-_n 1); // 1表示中位数要提取给父亲//提取中位数给父亲K newmid cur-_keys[mid];cur-_keys[mid] K();// 分裂的是根节点if (cur-_parent nullptr){_root new Node;_root-_keys[0] newmid;_root-_subs[0] cur;_root-_subs[1] brother;_root-_n 1;cur-_parent _root;brother-_parent _root;return true;}else //分裂的是叶子节点或者分支节点{// 转换成往cur-parent 去插入cur-[mid] 和 brothercur cur-_parent;newkey newmid;child brother;}}}
}4.5 插入key的过程
按照直接插入排序的思想插入key移动key也要移动它的右孩子最后在把中位数和孩子插入。
void InsertKey(Node* node, const K key, Node* child)
{int end node-_n - 1;while (end 0){if (key node-_keys[end]){//插入 挪动key和它的右孩子node-_keys[end 1] node-_keys[end];node-_subs[end 2] node-_subs[end 1];--end;}else{break;}}node-_keys[end 1] key;node-_subs[end 2] child;if (child)//细节别忘记,我们有父指针child-_parent node;
}4.7 B树的插入完整代码
templateclass K,size_t M
struct BTreeNode
{//K _keys[M - 1];//BTreeNodeK, M* _subs[M];// M叉树即一个节点最多有M-1个关键字,M个孩子// 为了方便插入以后再分裂多给一个空间K _keys[M];BTreeNodeK, M* _subs[M 1];size_t _n;//记录实际存储多少个关键字BTreeNodeK, M* _parent;//父指针BTreeNode(){for (size_t i 0; i M; i){_keys[i] K();_subs[i] nullptr;}_subs[M] nullptr;_parent nullptr;_n 0;}};//数据是存在磁盘K是磁盘地址
templateclass K,size_t M
class BTree
{typedef BTreeNodeK, M Node;
public:// 返回值: Node代表找到的节点,int为该元素在该节点中的位置pairNode*, int Find(const K key){// 从根节点的位置开始查找Node* cur _root;Node* parent nullptr;while (cur)// 节点存在{// 在一个节点查找size_t i 0;while (i cur-_n){if (key cur-_keys[i])// 该元素可能在i的左边的孩子节点中{break;}else if (key cur-_keys[i])// 继续向右查找,越界后往最后一个关键字的右孩子去找{i;}else{return make_pair(cur, i);// 找到返回}}//往孩子去跳parent cur;cur cur-_subs[i];}//没找到,把叶子节点返回去return make_pair(parent, -1);}void InsertKey(Node* node, const K key, Node* child){int end node-_n - 1;while (end 0){if (key node-_keys[end]){//插入 挪动key和它的右孩子node-_keys[end 1] node-_keys[end];node-_subs[end 2] node-_subs[end 1];--end;}else{break;}}node-_keys[end 1] key;node-_subs[end 2] child;if (child)//细节别忘记,我们有父指针child-_parent node;}bool Insert(const K key){// 如果树为空直接插入if (_root nullptr){_root new Node;_root-_keys[0] key;_root-_n 1;return true;}// 找插入位置如果key已经存在则不插入auto ret Find(key);if (ret.second 0){return false;}// 如果没有找到Find顺便带回了要插入的那个叶子节点// 循环每次往cur插入 newkey和childNode* cur ret.first;Node* child nullptr;K newkey key;while (1){InsertKey(cur, newkey, child);// 满了就要分裂// 没有满插入就结束if (cur-_n M){return true;}else{size_t mid M / 2;// 申请兄弟节点,分裂一半给兄弟 [mid 1, M - 1]Node* brother new Node;size_t j 0;size_t i mid 1;for (; i M; i){// 分裂拷贝key和key的左孩子给兄弟 (分裂的是叶子节点没有孩子,分支节点和根节点都有孩子)brother-_keys[j] cur-_keys[i];brother-_subs[j] cur-_subs[i];// 如果孩子存在,分裂孩子给兄弟之后,孩子的父指针指向兄弟if (cur-_subs[i]){cur-_subs[i]-_parent brother;}j;// 拷走重置一下方便观察cur-_keys[i] K();cur-_subs[i] nullptr;}//最后一个右孩子也要拷贝给兄弟brother-_subs[j] cur-_subs[i];//孩子的父指针指向兄弟if (cur-_subs[i])cur-_subs[i]-_parent brother;cur-_subs[i] nullptr;//更新节点关键字个数brother-_n j;cur-_n - (brother-_n 1); // 1表示中位数要提取给父亲//提取中位数给父亲K newmid cur-_keys[mid];cur-_keys[mid] K();// 分裂的是根节点if (cur-_parent nullptr){_root new Node;_root-_keys[0] newmid;_root-_subs[0] cur;_root-_subs[1] brother;_root-_n 1;cur-_parent _root;brother-_parent _root;return true;}else //分裂的是叶子节点或者分支节点{// 转换成往cur-parent 去插入cur-[mid] 和 brothercur cur-_parent;newkey newmid;child brother;}}}}private:Node* _root nullptr;
};4.8 B树的简单验证
对B树进行中序遍历如果能得到一个有序的序列说明插入正确 void _InOrder(Node* root)
{if (root nullptr)return;// 左 根 左 根 ... 右size_t i 0;for (; i root-_n; i){_InOrder(root-_subs[i]);//左子树cout root-_keys[i] ;//根}_InOrder(root-_subs[i]);//最后的那个右子树
}4.9 B树的删除
B树的删除这里我们就不说了。如果对删除有兴趣请参考《算法导论》-- 伪代码和《数据结构-殷人昆》–C实现代码。不过这里我们可以说一下大思路。
当被删除关键字k在分支节点可以用k前序当前关键字左侧指针所指子树中 “最右下” 元素或者后继当前关键字右侧指针所指子树中 “最左下” 元素k’ 来代替 k然后就转化成在叶子节点删除关键字了因此下面我们讨论的是删除叶子节点关键字的情形。 当被在叶子节点删除分为下面4种情况
若被删除的关键字所在叶子结点同时又是根节点并且关键字个数大于等于 ceil (m/2)直接删除。 若被删除的关键字所在叶子结点不是根节点并且关键字个数大于等于 ceil (m/2)直接删除。 若被删除的关键字所在叶子结点删除前关键字个数 n ceil(m/2) - 1且此时时与该节点相邻的右(或左)兄弟结点的关键字个数 n ceil(m/2)则需要调整该节点、右(或左)兄弟结点及其双亲结点(父子换位法)以达到新的平衡。(兄弟够借) 若被删除关键字所在结点删除前的关键字个数 n ceil(m/2) - 1且此时与该节点相邻的左、右兄弟结点的关键字个数 n ceil(m/2) - 1则将关键字删除后与左(或右)兄弟结点及双亲结点中的关键字进行合并。兄弟不够借 在合并的过程中双亲结点的关键字个数会减1若其双亲结点是根结点且关键字个数减少至0则直接将根节点删除合并后的新结点成为根若双亲结点不是根结点且关键字个数减少到ceil(m/2) -2则又要与它自己的兄弟结点进行调整或合并操作并重复上述步骤直至符合B树的要求为止。 4.10 B树的性能分析
B树上搜索一个值时间复杂度最坏就是走高度次。
假设每层结点关键字都是满的设为M孩子也是M。忽略掉孩子比关键字多1。
设有h层一层一层下去这就是一个等比数列。 这里我们可以用错位相减法来算 不满的情况 对于一棵节点为N度为M的B树查找和插入需要 l o g M − 1 N log_{M-1}N logM−1N~ l o g M / 2 N log_{M/2}N logM/2N次比较这个很好证明对于度为M的B-树每一个节点的子节点个数为M/2 ~(M-1)之间因此树的高度应该在要 l o g M − 1 N log{M-1}N logM−1N和 l o g M / 2 N log{M/2}N logM/2N之间在定位到该节点后再采用二分查找的方式可以很快的定位到该元素。
B-树的效率是很高的对于N 62*1000000000个节点如果度M为1024则 l o g M / 2 N log_{M/2}N logM/2N 4即在620亿个元素中如果这棵树的度为1024则需要小于4次即可定位到该节点然后利用二分查找可以快速定位到该元素大大减少了读取磁盘的次数。
2-3查找树就是M 3的B树。
5. B树
B树总体来说还是非常依赖于搜索树还区分左孩子右孩子。并且分支节点孩子的数量比关键字多一个整体而言反而让结构变得复杂了不少。基于一系列原因大佬又对B树进行了优化。
B树是B树的变形是在B树基础上优化的多路平衡搜索树B树的规则跟B树基本类似但是又在B树的基础上做了以下几点改进优化
分支节点的子树指针与关键字个数相同分支节点的子树指针p[i]指向关键字值大小在[k[i]k[i1])区间之间所有叶子节点增加一个链接指针链接在一起所有关键字及其映射数据都在叶子节点出现
2孩子与关键字个数相等 3B树以前下标和我相等是我的左孩子现在在[k[i]k[i1])之间。 2、3合在一起相当于取消了最左边的那个子树。 4方便了去遍历不需要从根开始了。 5所有关键字及其映射数据都在叶子节点出现。这个时候不就有重复值了吗这个时候另外的隐含意思是
分支节点根叶子节点有重复的值分支节点存的是叶子节点索引。 父亲中存的是孩子节点中的最小值做索引。 比如在这颗B树搜索一个33是如何搜索的呢 先找到根如果比5还小根本不存在5已经是最小的了。 如果比5大往下一个。比28大还往下一个。比65小说明在65的左边。去P2找。 比28大往下一个比35小说明在55的左边。去P1找。最终找到33。如果是34最终就是去33的右孩子去找但33右孩子是空所以找不到。 插入的过程也是类似的。这里简单了解一下 M 3 B树分裂过程它这里的结构搞的简单一些。
刚开始插入要两层节点一层做分支一层做根。
插入到139。目前关键字是3个了。因为B树分支节点孩子和关键字个数相同所以不用分裂。只有当 关键字个数 M 才分裂 插入 49关键字个数 M 分裂 插入满了之后分裂一半给兄弟转换成往父亲插入一个key和一个孩子孩子就是兄弟key就是兄弟的第一个最小值的key。 插入14536 插入101第二次分裂 再来两个数150、155我们看看连续分裂的情况 B树插入过程
B树的插入过程根B树基本是类型的细节区别在于第一次插入两层节点一层做分支一层做根。后面一样往叶子去插入插入满了之后分裂一半给兄弟转换成往父亲插入一个key和一个孩子孩子就是兄弟key就是兄弟的第一个最小值的key。
总结一下B树
简化B树孩子比关键字多一个的规则变成相等所有值都在叶子节点方便遍历查找所有值
B树的特性
所有关键字都出现在叶子节点的链表中且链表中的节点都是有序的。不可能在分支节点中命中。分支节点相当于是叶子节点的索引叶子节点才是存储数据的数据层。
6. B*树
B*树是B树的变形
在B树的分支节点增加指向兄弟节点的指针。B树节点原来关键字个数最少是1/2MB*树要求节点关键字最少是2/3M最多是M。
B树的分裂
当一个结点满时分配一个新的结点并将原结点中1/2的数据复制到新结点最后在父结点中增加新结点的指针B树的分裂只影响原结点和父结点而不会影响兄弟结点所以它不需要指向兄弟的指针。
B*树最大的改变就是让每个节点更满。因为B树和B树都有一个缺陷可能会浪费一半的空间。
B*树的结点关键字和孩子数量 - [2/3MM]。
B*树的分裂
当一个结点满时如果它的下一个兄弟结点未满那么将一部分数据移到兄弟结点中再在原结点插入关键字最后修改父结点中兄弟结点的关键字因为兄弟结点的关键字范围改变了如果兄弟也满了则在原结点与兄弟结点之间增加新结点并各复制1/3的数据到新结点最后在父结点增加新结点的指针。 所以B*树分配新结点的概率比B树要低空间使用率更高
7. 总结
通过以上介绍大致将B树B树B*树总结如下
B树有序数组平衡多叉树 B树有序数组链表平衡多叉树 B*树一棵更丰满的空间利用率更高的B树
8. B树的应用
B树的应用有两个一个是文件系统一个是索引。
B树的应用有些人做了对比在内存中 做内查找。B树系列和哈希和平衡搜索树对比。
单论树高度搜索效率而言B树确实不错。但是B树系列有一些隐形坏处
空间利用率低消耗高插入删除数据时分裂和合并节点那么必然挪动数据虽然高度更低但是在内存中而言跟哈希和平衡搜索树还是一个量级 结论实质上B树系列在内存中体现不出优势。
8.1 索引
B树最常见的应用就是用来做索引。索引通俗的说就是为了方便用户快速找到所寻之物比如书籍目录可以让读者快速找到相关信息hao123网页导航网站为了让用户能够快速的找到有价值的分类网站本质上就是互联网页面中的索引结构。
MySQL官方对索引的定义为索引(index)是帮助MySQL高效获取数据的数据结构简单来说索引就是数据结构。
当数据量很大时为了能够方便管理数据提高数据查询的效率一般都会选择将数据保存到数据库因此数据库不仅仅是帮助用户管理数据而且数据库系统还维护着满足特定查找算法的数据结构这些数据结构以某种方式引用数据这样就可以在这些数据结构上实现高级查找算法该数据结构就是索引。
8.2 MySQL索引简介
mysql是目前非常流行的开源关系型数据库不仅是免费的可靠性高速度也比较快而且拥有灵活的插件式存储引擎如下 数据库有一个CathesBuffers意思是数据存在磁盘中直接访问太慢 所以建一个缓存(可以考虑使用LRU)。对于B树而言可以把所有分支节点存储到Cache里搜索必然要走分支。如果使用B树缓存就没有多大意义因为太大了分支节点既有数据也要数据所在磁盘的地址。B树相比于B树而言分支节点只存key分支节点比较小。分支节点映射的磁盘数据块就可以尽量加载Cache。
倒数第二行是数据库的搜索引擎。
MySQL中索引属于存储引擎级别的概念不同存储引擎对索引的实现方式是不同的。
注意索引是基于表的而不是基于数据库的。
数据库创建好了建表的时候其实就要建立一颗B树。
比如下面这张表的信息存到磁盘那如何能快速查找信息呢
这个时候B树就可以起作用了不过最好还是用B树是最好的。
数据库创建好了首先要建表建表要指定列字段和属性通常要指定一个主键不然就用默认主键等等。建表的主键就是B树的key。B树的value是存储一行数据的磁盘地址。 分支节点也是需要存磁盘中的因为数据量大了内存是存不下的。分支节点中应该是磁盘的地址。但是分支节点理论应该尽量被缓存到cache。
对表的操作有增删查改比如我们改。可以有两种方式一种是条件筛选使用主键另一种是使用其他字段。思考一下这两种写法有何差别 第一种可以使用B树进行查找效率高时间复杂度O(logmn) 第二种只能遍历B树所有叶子节点暴力查找效率低时间复杂度O(n) (全表扫描)
如果经常向使用name去进行查找怎么办 其实可以用name创建一个索引。 对name创建索引之后相当于使用B树用name做key创建一棵树当然value指向磁盘数据那么在执行对应的sql语句效率就高了 一般数据库要求主键值是不重复的唯一值字段电话、身份证号码适合名字、地址不适合。没有字段能保持唯一可以考虑自增主键其实就是它自己建立一个自增整数做主键
如果主键冲突插入数据就会报错。
一般数据库不要求索引唯一像mysql建立索引可以考虑使用B树或者哈希表数据结构允许冗余。
B树做主键索引相比于B树优势
B树所有值都在叶子节点遍历很方便方便区间查找对于没有建立索引的字段全表扫描的遍历很方便分支节点值存储key一个分支节点空间占用更小可以尽可能加载到内存
B树不用到叶子就能找到值B树一定要到叶子这是B树一个优势但是B树高度足够低所以差别不大。
8.2.1 MyISAM
MyISAM引擎是MySQL5.5.8版本之前默认的存储引擎不支持事务支持全文检索使用BTree作为索引结构叶节点的data域存放的是数据记录的地址其结构如下 上图是以以Col1为主键MyISAM的示意图可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中主索引和辅助索引Secondary key在结构上没有任何区别只是主索引要求key是唯一的而辅助索引的key可以重复。如果想在Col2上建立一个辅助索引则此索引的结构如下图所示
叶节点的data域存放的是数据记录的地址方便索引树和主键树映射同样的数据。 说明B树节点数据都在磁盘文件中访问节点都是IO行为只是它会把热数据缓存到cache。
同样也是一棵BTreedata域保存数据记录的地址。因此MyISAM中索引检索的算法为首先按照BTree搜索算法搜索索引如果指定的Key存在则取出其data域的值然后以data域的值为地址读取相应数据记录。MyISAM的索引方式也叫做“非聚集索引”的。
8.2.2 InnoDB
InnoDB存储引擎支持事务其设计目标主要面向在线事务处理的应用从MySQL数据库5.5.8版本开始InnoDB存储引擎是默认的存储引擎。InnoDB支持B树索引、全文索引、哈希索引。但InnoDB使用BTree作为索引结构时具体实现方式却与MyISAM截然不同。
第一个区别是InnoDB的数据文件本身就是索引文件。MyISAM索引文件和数据文件是分离的索引文件仅保存数据记录的地址。而InnoDB索引表数据文件本身就是按BTree组织的一个索引结构这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键因此InnoDB表数据文件本身就是主索引。 上图是InnoDB主索引同时也是数据文件的示意图可以看到叶节点包含了完整的数据记录这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集所以InnoDB要求表必须有主键MyISAM可以没有如果没有显式指定则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键如果不存在这种列则MySQL自动为InnoDB表生成一个隐含字段作为主键这个字段长度为6个字节类型为长整型。
这样建立索引有一个不好的地方。建立索引的时候索引树的叶子节点和主键树叶子节点中数据不一样没办法直接映射 第二个区别是InnoDB的辅助索引data域存储相应记录主键的值而不是地址所有辅助索引都引用主键作为data域 聚集索引这种实现方式使得按主键的搜索十分高效但是辅助索引搜索需要检索两遍索引首先检索辅助索引获得主键然后用主键到主索引中检索获得记录。
参考资料 MySQL索引背后的数据结构及算法原理
