B树的预备知识
我们平常查找比如用搜索二叉树哈希表这些数据结构,一般都是数据在内存中的,这样的话访问数据的速度就很快,这种查找也叫做内查找。二分查找或者直接顺序查找也适合内查找。
但是当数据量非常大时,比如有100G的数据,此时内存就放不下了,只能放在磁盘上了,在内存外的存储结构上查找也就是外查找。
对于外查找以我们之前所学习的知识,该用什么思路呢?
数据在磁盘中,并且是连在一起的,它们也有地址。我们可以用一个平衡搜索树存每个数据的地址,这样每次查找我们需要通过一次文件IO将地址转化成数据进行比较,然后再向下进行。这样的话查找起来主要耗时就在磁盘IO上,如果是这种结构,那么就需要高度次IO,也就是O(logN)级别,比如AVL/红黑树。或者我们也可以用哈希表,它是O(1)级别的,但是哈希表在极端场景下哈希冲突非常严重,也会导致效率低下。
而且磁盘慢主要是它的每一次查找定位很慢,一旦定位到了就很快了,这跟之后B树设计有关系。
B树就是在搜索树的基础上进行优化的:
1.压缩高度,二叉变多叉
2.一个结点要存多个关键字及映射的值。
B树的概念
1970年,R.Bayer和E.mccreight提出了一种适合外查找的树,它是一种平衡的多叉树,称为B树 (后面有一个B的改进版本B+树,然后有些地方的B树写的的是B-树,注意不要误读成"B减树")。一 棵m阶(m>2)的B树,是一棵平衡的M路平衡搜索树,可以是空树或者满足一下性质: 1. 根节点至少有两个孩子 2. 每个分支节点都包含k-1个关键字和k个孩子,其中 ceil(m/2) ≤ k ≤ m ceil是向上取整函数 3. 每个叶子节点都包含k-1个关键字,其中 ceil(m/2) ≤ k ≤ m 4. 所有的叶子节点都在同一层 5. 每个节点中的关键字从小到大排列,节点当中k-1个元素正好是k个孩子包含的元素的值域划分 6. 每个结点的结构为:(n,A0,K1,A1,K2,A2,… ,Kn,An)其中,Ki(1≤i≤n)为关键 字,且Ki不过需要注意的是,一般我们会多开一个空间,以此来方便后续关键字满了后要分裂的场景,比如
m依旧为3,但是结点如下
在实际设计中,M的值一般会设计的很大,比如1024
B树的插入
首先我们知道,一个结点中,关键字的顺序是从小到大排序的,那么当结点中的关键字没有满时,我们就需要找到这个关键字适合插入的位置。
如果结点满了,那么这个结点就需要分裂出一个兄弟结点,并将自己一半的关键字和孩子分给这个兄弟结点。然后再选一个中位数大小的关键字给父亲结点(也要注意顺序),然后将兄弟结点与父亲结点进行连接,如果父亲结点不存在,那么就先创建一个父亲结点,然后记得连接子结点。
后续插入就是以此类推,从父结点开始找,根据大小一直找到对应的叶子结点,然后再插入,如果满了就分裂。B树的新结点的插入一定是在叶子结点上的。叶子没有孩子,不影响关键字和孩子的关系,叶子结点满了,就分裂出一个兄弟,再提取中位数,向父亲结点插入这个关键字,和一个孩子(也就是兄弟结点)。
由此我们可以发现,B树是天然平衡的,因为它的生长是向右和向上生长的。
B树的简单实现
#pragma once #include#include using namespace std; template struct BTreeNode { // 为了方便插入以后再分裂,可以多给一个空间 K _keys[M]; // 存关键字的 BTreeNode * _subs[M + 1]; // 存孩子的指针 BTreeNode * _parent; // 也是方便插入时找到父亲结点 size_t _n; // 记录实际存储了多少个关键字 BTreeNode() { for (size_t i = 0; i < M; ++i) { _keys[i] = K(); _subs[i] = nullptr; } _subs[M] = nullptr; _parent = nullptr; _n = 0; } }; // 这里我们简化代码,只实现K模型的而不是K-V模型的 // 外查找时数据存在磁盘里,那么肯定得是K-V模型。 template class BTree { typedef BTreeNode Node; public: pair Find(const K& key) { Node* parent = nullptr; Node* cur = _root; while (cur) { // 在一个结点中查找 size_t i = 0; while (i < cur->_n) { if (key < cur->_keys[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); // 到叶子结点了,这个-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]; // 注意key和它的右孩子的对应关系 --end; } else { break; } } // 插入 node->_keys[end + 1] = key; node->_subs[end + 2] = child; if (child) { child->_parent = node; } node->_n++; } bool Insert(const K& key) { if (_root == nullptr) // 第一次插入 { _root = new Node; _root->_keys[0] = key; _root->_n++; return true; } // 先查找,如果key已经存在,那么就不用插入了。 pair ret = Find(key); if (ret.second >= 0) // 说明已存在 { return false; } // 如果没有找到,find也带回了要插入的那个叶子结点 // 循环每次往cur插入 newkey和child Node* parent = ret.first; K newKey = key; Node* child = nullptr; while (1) { InsertKey(parent, newKey, child); // 没有满,插入就结束 if (parent->_n < M) // 这里就对应了为什么在Node里要多开一个空间。 { 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; // 这里为什么要+1,是因为还要拿一个结点给父亲 for (; i <= M - 1; ++i) { // 分裂拷贝key和key的左孩子 brother->_keys[j] = parent->_keys[i]; brother->_subs[j] = parent->_subs[i]; if (parent->_subs[i]) { parent->_subs[i]->_parent = brother; } ++j; // 方便观察 parent->_keys[i] = K(); parent->_subs[i] = nullptr; } // 注意 还有最后一个右孩子拷给兄弟 brother->_subs[j] = parent->_subs[i]; if (parent->_subs[i]) { parent->_subs[i]->_parent = brother; } parent->_subs[i] = nullptr; brother->_n = j; parent->_n -= (brother->_n + 1); // 为什么要+1因为还有一个要给父亲 K midKey = parent->_keys[mid]; // 准备给父亲结点插入key了 parent->_keys[mid] = K(); // 说明刚刚分裂是根结点 if (parent->_parent == nullptr) { _root = new Node; _root->_keys[0] = midKey; _root->_subs[0] = parent; _root->_subs[1] = brother; // 写到这里再回想一下,B树的规则:根结点至少有两个孩子 _root->_n = 1; parent->_parent = _root; brother->_parent = _root; break; } else { // 如果不是根结点,那么就往父亲结点插入,以此循环,直到新建了一个根结点 // 或者在下一次插入的父亲结点中,在插入后未满 newKey = midKey; child = brother; parent = parent->_parent; } } } return true; } 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]); } void InOrder() // 中序遍历 将数据有序输出 { _InOrder(_root); } private: Node* _root = nullptr; }; void TestBtree() { int a[] = { 53, 139, 75, 49, 145, 36, 101 }; BTree t; for (auto e : a) { t.Insert(e); } t.InOrder(); }
这中间还有一个中序遍历,其实也非常简单,二叉树的中序遍历是 左 根 右。而这里B树的遍历就是 左 根 左 根 .... 右,就是最后再补一个右即可。
B+树
B+树的概念
B+树是B树的变形,是在B树基础上优化的多路平衡搜索树,B+树的规则跟B树基本类似,但是又 在B树的基础上做了以下几点改进优化: 分支节点的子树指针与关键字个数相同。 分支节点的子树指针p[i]指向关键字值大小在[k[i],k[i+1])区间之间。 所有叶子节点增加一个链接指针链接在一起。 所有关键字及其映射数据都在叶子节点出现。
由图我们可以看到,叶子结点是链接在一起的,这样话我们也可以直接遍历叶子结点来找到我们想要的数据。
分支节点里面都只存Key,只有叶子节点里面才存Key和Val。
分支结点根叶子结点有重复的值,分支结点存的是叶子结点的索引。
父亲结点存的是孩子结点中最小的值作为索引。
所以现在可以做一个小小的总结:
1.B+树简化了B树孩子比关键字多一个的规则,B+树的关键字和孩子数量相等。
2.父亲中存的孩子结点中最小的值作为索引。
B+树的插入
B+树的插入跟B树相似,但又略有不同,这里就只说思想了。
但是我们知道,B+树的分支结点只存Key,叶子结点既存Key也存Val。因此,在第一次插入的时候,B+树就有两层!一层做根,一层做叶子。我们依旧以M=3为例
第一次插入53
一直插入直到49开始第一次分裂
这里的处理也比B树简单一些,它是直接将一半的索引给分裂出来的兄弟结点,然后直接将兄弟的最小值给父亲结点作为索引。
接下来一直插入,直到插入101进行第二次分裂
第二次分裂与第一次逻辑一样。
接下来再补充插入一些结点(150和155),来看看第三次分裂
此时我们发现分裂后,父亲结点满了,那么父亲结点也需要进行分裂
这样B+树就由最初的两层变成了三层。
这就是B+树的插入思想。
总结B+树的特性:
1. 所有关键字都出现在叶子节点的链表中,且链表中的节点都是有序的。 2. 不可能在分支节点中命中。因为分支节点中存的是Key。 3. 分支节点相当于是叶子节点的索引,叶子节点才是存储数据的数据层。 实际上,B+树的应用比B树要广泛很多。B*树
B*树又是在B+树的基础上作出了新的规则。与B+树不同的是,B*树在非根和非叶子结点中也增加了指向兄弟结点的指针。 我们来总结一下B+树的分裂: 当一个结点满时,分配一个新的结点,并将原结点中1/2的数据复制到新结点,最后在父结点中增 加新结点的指针;B+树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向 兄弟的指针。再来说说B*树的分裂:
当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结 点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);如 果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点,最后在父 结点增加新结点的指针。 所以,B*树分配新结点的概率比B+树要低,空间使用率更高; 注意:B*树结点关键字数量的范围是[2/3M,M],因此分裂的时候自己和兄弟各自凑出1/3M,给新的兄弟结点。
总结三种树
B 树:有序数组 + 平衡多叉树; B+ 树:有序数组链表 + 平衡多叉树; B* 树:一棵更丰满的,空间利用率更高的 B+ 树。 实际应用中还是B+树使用的更为广泛。
B-树的应用
B-树在内查找和外查找中的表现
内查找
内查找也就是在内存中查找。
B树系列和哈希表和平衡搜索树(AVL树和RB树)的对比:
如果只看树的高度,和搜索效率的话,B树系列确实不错。
但是B树系列也有缺点:
1.空间利用率低,消耗大。我们可以看到很多结点都不一定会存满。
2.插入数据和删除数据时,会分裂和合并结点,那么必然就会挪动数据,带来隐形的消耗。
3.虽然B树系列高度低,但是就在内存中而言,跟哈希和平衡搜索树还是一个量级的。
总结:B树系列在内存中体现不出优势。
外查找
但是,在外查找,也就是磁盘中就不一样了。
在内存中查找3次和30次,差距并不大。
但是在磁盘中查找3次和30次差距就很大了。
因为我们知道IO操作是很消耗时间的。
因此B树系列在外查找中就能体现出优势。
索引
B-树最常见的应用就是用来做索引。索引通俗的说就是为了方便用户快速找到所寻之物,比如: 书籍目录可以让读者快速找到相关信息,hao123网页导航网站,为了让用户能够快速的找到有价 值的分类网站,本质上就是互联网页面中的索引结构。 MySQL官方对索引的定义为:索引(index)是帮助MySQL高效获取数据的数据结构,简单来说: 索引就是数据结构。 当数据量很大时,为了能够方便管理数据,提高数据查询的效率,一般都会选择将数据保存到数 据库,因此数据库不仅仅是帮助用户管理数据,而且数据库系统还维护着满足特定查找算法的数 据结构,这些数据结构以某种方式引用数据,这样就可以在这些数据结构上实现高级查找算法, 该数据结构就是索引。
其中B-树的一般就是做MyISAM或InnoDB的搜索引擎的。
一般是B+树用来做磁盘数据索引的。
比如我们要创建一个学生的信息表,有学生ID,年龄等信息。
在创建的时候,我们还需要选择一个信息作为主键,也就是将来搜索时的关键字。有些数据库不准用名字作为主键,因为名字可能不唯一,比如Mysql,但是有些数据库可以。
比如这里我们拿学生ID作为主键。那么ID就是Key,Val就是这个学生所有的信息的磁盘地址(这个信息一般就是一行)。
另外分支结点也是需要存在磁盘中的,因为数据量大了的话,内存中也存不下。但是分支结点理应被缓存到cache中。
另外当我们在查询数据的时候,我们可以根据ID来找,也可以根据姓名来找。但是ID是主键,用ID来查找的效率要比按姓名来查找的效率要高很多。用主键来查找的效率是 O(logN),而用非主键的信息来查找的效率就是 O(N),因为它是通过遍历叶子结点来进行查找的。
但是如果我们又经常使用姓名去查找的话,我们可以用姓名建立一个索引。
当姓名也就是name索引创建以后,那么就会以B+树以name作为key再创建一颗树。这样的话效率就高了。
mysql的存储引擎
MyISAM引擎是MySQL5.5.8版本之前默认的存储引擎,不支持事物,支持全文检索,使用B+Tree 作为索引结构,叶节点的data域存放的是数据记录的地址。 InnoDB存储引擎支持事务,其设计目标主要面向在线事务处理的应用,从MySQL数据库5.5.8版 本开始,InnoDB存储引擎是默认的存储引擎。InnoDB支持B+树索引、全文索引、哈希索引。但 InnoDB使用B+Tree作为索引结构时,具体实现方式却与MyISAM截然不同。 第一个区别是InnoDB的数据文件本身就是索引文件。MyISAM索引文件和数据文件是分离的, 索引文件仅保存数据记录的地址。而InnoDB索引,表数据文件本身就是按B+Tree组织的一个索 引结构,这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键,因此 InnoDB表数据文件本身就是主索引。