做网站业务的 怎么跑客户,男女做那个视频网站,网络营销服务概念,上海网络推广需要多少目录 一. 常见的搜索结构
二. B树的概念
三. B树节点的插入和遍历
3.1 插入B树节点
3.2 B树遍历
四. B树和B*树
4.1 B树
4.2 B*树
五. B树索引原理
5.1 索引概述
5.2 MyISAM
5.3 InnoDB
六. 总结 一. 常见的搜索结构
表示1为在实际软件开发项目中#xff0c;常用…目录 一. 常见的搜索结构
二. B树的概念
三. B树节点的插入和遍历
3.1 插入B树节点
3.2 B树遍历
四. B树和B*树
4.1 B树
4.2 B*树
五. B树索引原理
5.1 索引概述
5.2 MyISAM
5.3 InnoDB
六. 总结 一. 常见的搜索结构
表示1为在实际软件开发项目中常用的查找结构和方法包括顺序查找、二分查找、二叉搜索树、平衡二叉树、哈希表等这几种查找方法和数据结构都适合于内查找将数据加载到内存中查找。
搜索结构数据要求时间复杂度顺序查找无要求O(N)二分查找顺序排序O(logN)二叉搜索树无要求O(N)平衡二叉树无要求O(logN)哈希表无要求O(1)
如果数据量极大内存无法存放时就需要将数据存储在磁盘当中而CPU访问磁盘的速度要远远低于访问内存的速度假设O(1)的时间复杂度下要执行2次访问O(logN)的时间复杂度下要执行30次访问。如果对内存数据进行访问因为访问内存速度相对较快所有我们可以认为O(1)和O(logN)时间复杂度算法的性能是一致的。但是如果是对于磁盘上的数据的访问由于磁盘数据访问的效率较低因此O(1)和O(logN)差别会很大。
采用二叉搜索树检索磁盘数据的缺陷为
二叉搜索树查找的时间复杂度为O(logN)磁盘IO效率低O(logN)的时间复杂度相对于O(1)会很大程度上降低性能。
但是哈希查找的时间复杂度是O(1)为什么哈希也不适用于对磁盘数据的检索呢这是因为哈希的有这样的缺陷
在极端情况下哈希表中会产生大量的哈希冲突查找的时间复杂度会接近O(N)。虽然很多时候当哈希冲突达到一定数量时在哈希散列中会由挂单链表改为挂红黑树但红黑树查找的时间复杂度依旧是O(logN)。
为了解决平衡二叉树和哈希表无法很好的应对内存数据查找的情况B树被创造和出来B树适用于对磁盘中大量的数据进行检索当然B树也能够在内存在查找数据但效果就不如哈希和平衡二叉树。
由于B树/B树适用于检索磁盘中大量数据的性质经常被用于作为数据库的底层检索结构。
二. B树的概念
B树是一种适合外查找的平衡多叉树一颗m阶的B树是一颗m路的二叉搜索树一颗B树要么为空树要么满足如下几个条件
根节点至少有两个孩子节点。分支节点非叶子节点应当有K-1个键值和K个孩子节点其中其中ceil为向上取整函数。所有叶子节点都在同一层。每个节点中的键值都是自小到大升序排序的键值Key表示子树的阈值划分。对于任意一个节点孩子节点的数目总是比键值多一个。
图2.1就是一颗3阶B树注意观察其根节点两个键值为50和100根节点的第一个孩子节点键值全部小于50第二个孩子节点的键值位于(51,100)之间第三个孩子节点键值大于100这就是键值Key的阈值划分功能。
B树检索与二叉搜索树的检索类似假设我们要在图2.1所示的B树中检索99先从根节点开始找起对比待查找的值和键值的大小发现其位于(50,100)范围内这样就向下遍历查找p2子树在p2子树的键值中找到了键值99检索完成。 图2.1 3阶B树 三. B树节点的插入和遍历
3.1 插入B树节点
由于B树的插入操作过于抽象因此直接上实例在示例中讲解B树节点插入的具体操作。假设依次将std::vectorint v { 53,139,75,49,145,36,50,47,101}插入到3阶B树中。为了方便插入操作我们在申请B树节点空间的时候阶数为M就为键值申请M个空间为孩子节点申请M1个空间这样做的目的是方便插入时数据挪动以及后面的分裂操作。
① 插入53
53是B树插入的第一个节点因此直接将其插入到根节点的第一个键值位置处即可。如果3.1所示插入53后有一个B树根节点这个根节点附带有两个孩子节点nullptr。这里的根节点也是叶子节点注意B树插入新节点一定是向叶子节点插入的。 图3.1 插入B树的第一个节点53 ② 插入139
139大于53且插入后根节点叶子结点中键值的数目不超过M-1因此只需将139至于53的后面并且带入null子节点即可。 图3.2 插入第二个节点139后的B树结构 ③ 插入75
75位于53和139之间所以第一步要现将75插入到root节点的这两个值之间。但是插入75后root节点就有了3个键值这样就不符合B树的结构要求需要进行分裂。
分裂操作的步骤为
取中间位置mid M/2下标处为分界线创建一个兄弟节点brother将下标位于[mid1,M)的键值及其左右孩子都拷贝到brother节点中去设下标为键值相同的孩子节点为左孩子比键值下标大1的孩子节点称为右孩子。将mid处的键值交给其父亲节点如果没有父亲节点节创建父亲节点父亲节点的其中两个孩子节点就包含原先发生分裂的节点以及分裂出的节点brother。 图3.3 插入第三个节点75后的结构及B树的分裂操作 ④ 插入49
首先检索节点插入的位置发现49小于根节点root的第一个键值因此找到n1节点n1节点为叶子节点可以执行插入操作49小于第一个节点53所以应当将53向后移动一位并将49设置为n1节点的第一个键值。 图3.4 插入B树第四个节点49 ⑤ 插入145
首先检索插入数据的叶子节点根节点只有一个键值75145大于75向n2节点查找n2为叶子节点可以执行插入操作将145插入到139后面插入过后键值个数少于阶数M不用分裂。 图3.5 插入B树第五个节点49 ⑥ 插入36
查找36的插入位置应该为图3.5中的n1节点将35插入n1后n1有3个键值需要进行分裂兄弟节点取走5349向上交给n1的父亲节点分裂出的兄弟节点要作为root节点的一个孩子节点。 图3.6 插入新节点36及分裂操作 ⑦ 插入50
直接找到n2节点插入到键值53之前即可。 图3.7 插入新节点53 ⑧ 插入47 插入到n1节点46的后面即可。 图3.8 插入新节点47 ⑨ 插入101
先初步执行插入操作即101插入到n3节点的第一个键值位置处插入后n3节点的键值数量达到了阶数M要执行分裂操作。然而分裂后将mid处键值交给父亲节点root管理后root的键值数量也达到了阶数M需要进一步分裂更新root。 图3.9 插入新节点101 3.2 B树遍历
B树是一种特殊的搜索树如果按照中选遍历那么理应得到升序的一组数据B树遍历的方法与普通的二叉搜索树中序遍历并没有本质区别区别在于M路遍历和双路遍历。图3.10为二叉搜索树的遍历流程图遍历得到升序排序结果。 图3.10 B树前序遍历的递归路径图 代码3.1插入B树节点和前序遍历B树
#include iostream// B树节点K为索引数据类型M为最大阶数
templateclass K, size_t M
struct BTreeNode
{// 存储键值和孩子节点的一维数组// K _key[M - 1];// BTreeNodeK, M _sub[M];// 为了方便后续的分裂和插入操作多开辟一个空间K _key[M];BTreeNodeK, M* _sub[M 1];BTreeNodeK, M* _parent; // 父亲节点size_t _n; // 键值个数// 构造函数BTreeNode(): _parent(nullptr), _n(0){// 键值全部清零孩子节点全部为空for (size_t i 0; i M; i){_key[i] K();_sub[i] nullptr;}_sub[M] nullptr;}
};templateclass K, size_t M
class BTree
{typedef BTreeNodeK, M Node; // B树节点类型重定义
public:// 插入位置查找函数std::pairNode*, int Find(const K key){Node* parent nullptr;Node* cur _root;while (cur){// 在本层中查找大于key的键值如果找到这样的键值或者走到了最后一个键值// 那么就到下一层去查找如果找到与key相同的键值那么就直接返回该位置对应pairsize_t i 0;while (i cur-_n){// 键值按照升序排序逐个向后查找即可if (key cur-_key[i]) {i;}else if (key cur-_key[i]){break;}else // 存在相等就直接返回{return std::make_pair(cur, i);}}parent cur;cur cur-_sub[i];}return std::make_pair(parent, -1);}// 在一个B树节点值插入新键值的函数void InsertKey(Node* parent, const K key, Node* child){int end parent-_n - 1;while (end 0){if (parent-_key[end] key){// 将大于key的键值及其对应的右孩子节点全部向后移动一位parent-_key[end 1] parent-_key[end];parent-_sub[end 2] parent-_sub[end 1];--end;}else{break;}}// 将新的key值插入到end1位置处并引入右孩子节点parent-_key[end 1] key;parent-_sub[end 2] child;parent-_n;}// 新节点键值插入函数bool Insert(const K key){// 特殊情况当前B树根节点为空插入的是第一个节点if (_root nullptr){_root new Node;_root-_key[0] key;_root-_n;return true;}// 查找要插入节点的位置std::pairNode*, int ret Find(key);// 如果对应ret.second0那说明key已经在B树中存在// B树不允许冗余因此直接返回falseif (ret.second 0){return false;}Node* parent ret.first;Node* child nullptr;K newKey key;// 向上插入满足条件就分裂while (true){InsertKey(parent, newKey, child);if (parent-_n M - 1){return true;}else // 需要进行分裂操作{size_t mid M / 2; // 中间节点// 将中间mid之后的键值全部交给新创建的brother节点Node* brother new Node;size_t j 0;for (size_t i mid 1; i M; i){// 将key及其左孩子交给brother节点brother-_key[j] parent-_key[i];brother-_sub[j] parent-_sub[i];// 如果左孩子节点不为空那么就要跟新其父亲为brotherif (parent-_sub[i] ! nullptr){parent-_sub[i]-_parent brother;}// 将parent节点中被挪走的key和sub清空parent-_key[i] K();parent-_sub[i] nullptr;j;}// 将最后一个右孩子节点插入到brother节点中brother-_sub[j] parent-_sub[M];if (parent-_sub[M] ! nullptr){parent-_sub[M]-_parent brother;}parent-_sub[M] nullptr;// 更新键值个数这里parent键值个数减去brother-_n 11是因为要把mid子节点交给父节点brother-_n j;parent-_n - (brother-_n 1);K midKey parent-_key[mid];parent-_key[mid] K();if (parent _root){_root new Node;_root-_key[0] midKey;_root-_sub[0] parent;_root-_sub[1] brother;parent-_parent _root;brother-_parent _root;_root-_n;return true;}else{newKey midKey;parent parent-_parent;brother-_parent parent;child brother;}}}return true;}void _InOrder(Node* root){if (root nullptr){return;}// 依次遍历每个节点的左孩子for (size_t i 0; i root-_n; i){_InOrder(root-_sub[i]);std::cout root-_key[i] ;}// 遍历最后一个右孩子节点_InOrder(root-_sub[root-_n]);}// 中序函数void InOrder(){// 子函数_InOrder(_root);}private:Node* _root nullptr;
};
四. B树和B*树
4.1 B树
B树是在B树上优化了的多路平衡搜索二叉树相比于B树B树进行了以下几点优化
每个节点的键值数量和孩子节点数量相同。孩子节点指针p[i]指向的子B树键值范围位于 [ k[i], k[i1] ) 之间。所有存储了有效键值的节点都在叶子节点上。所有叶子节点都被连接了起来。 图4.1 B树的结构 B树的节点插入与B树类似同样由于其过于抽象本文以具体的实例来展示B树节点插入的过程假设要将std::vectorint v { 53,139,75,49,145,36,101 }插入到阶数M3的B树中去插入的流程及操作如下
① 插入53
插入的第一个节点首先创建两层B树节点一层为根节点一层为叶子节点在根节点和叶子节点的第一个键值位置处插入元素53。和B树一样如果阶数为M就为键值和孩子节点都多开辟一个空间以方便数据挪到和节点分裂。 图4.2 向B树中插入第一个数据 ② 插入139
首先检索插入位置发现139大于根节点中唯一一个键值53因此向下遍历找到n1将新数据插入到53后面节点中键值个数尚未达到阶数不需要分裂。 图4.3 向B树中插入139 ③ 插入75
检索到75应该插入子节点n1中139向后挪一个单位75插入到53和139之间以保证键值升序。 图4.4 向B树中插入75 ④ 插入49
首先查找可以插入49的叶子节点检索到插入位置为第一个键值位置因此要更新其父亲节点中对应位置的索引值这样root的第一个键值就由53变为了49。同时由于n1中的键值个数已经超过了阶数M所以要对这个节点执行分裂操作。 图4.5 插入数据49及B树的分裂 B树节点分裂操作
创建兄弟节点brother将分裂节点中后半部分键值挪动到brother中。并将brother中首个键值插入到父亲节点中将brother节点设为父节点的孩子节点。
⑤ 插入145
直接将145插入到节点n2中去因为插入后键值数量未超过B树的阶数不需要分裂。 图4.6 向B树中插入145 ⑥ 插入36
将36插入到n1的首个位置处然后更新器父亲节点对应的键值。B树中向叶子节点的首个关键字位置插入数据一定会更新父亲节点的索引 图4.7 向B树中插入36 ⑦ 插入101
将101插入到n2的键值75和39之间然后n2分裂。 图4.8 向B树中插入101 4.2 B*树
相比于B树B*树要求每个分支节点的键值利用率达到并且每一层节点又要存储指向其兄弟节点的指针B*树相对于B树最大的优化就是节省了空间能减少空间浪费。 图4.9 B*树的结构 五. B树索引原理
5.1 索引概述
索引就是通过某些关键信息让用户可以快速找到某些事物例如通过目录我们就可以快速检索到一本书中特定的内容所在的页码。B/B最普遍的用途就是做索引。
MySQL数据库官方给出的索引定义是索引index是帮助MySQL高效获取数据的数据结构。
当数据量很大的时候为了方便数据的管理、提高检索效率通常会将数据保存至数据库。数据库不仅仅要存储数据还要维护特定的数据结构和一些高效的搜索算法以帮助用户快速引用到某些数据。这种实现快速查找的数据结构就是索引。
MySQL是非常流行的开源关系型数据库不仅免费而且搜索效率较高可靠性高拥有灵活的插件式存储引擎在MySQL中索引是属于存储引擎范畴的概念不同的存储引擎对索引的实现方式是不同的。索引是基于表的而不是基于数据库的。
5.2 MyISAM
在早期的MySQL数据库中所使用的搜索引擎都是MyISAM这种搜索引擎不支持事务支持全文索引其使用的数据结构是B树。在MyISAM搜索引擎中叶子节点中的data域存储的是数据在磁盘中的地址而不是数据本身。如图5.1所示的学生信息管理数据库要记录学生的学号(StuId)、年龄(age)以及姓名B树用于检索图5.1中选取的主键为StuId。
在绝大部分数据库中一般要求加入到数据库中的数据要有一个主键并且主键是不允许出现重复的。就以图5.1所示的学生信息管理系统为例选取学号能保证每个学生之间的学号不重复而姓名和年龄则不可避免的出现重复那么就应当选取学号作为主键。如果没有一个合适的参数作为主键那么可以采用自增主键自增主键实际就是一个常数第一次插入的数据常数1为主键第二次插入的数据常数2为主键以此类推。 图5.1 MyISAM主键索引 以图如果用户通过主键索引查找数据库中的相关信息那么就会对B树进行检索直到检索到叶子节点发现匹配项或者确认数据库中没有对应主键即可。如果使用非主键未建立辅助索引的参数进行检索那么进行的操作是全表扫描查找匹配项。
对于MySQL数据库我们处理使用主键建立主索引之外还可以建立辅助索引主索引不允许出现重复项而辅助索引允许出现重复项如图5.2所示就是通过学生年龄age建立的学生数据库的辅助索引。 图5.2 已age为主键的MyISAM辅助索引 5.3 InnoDB
现在高版本的MySQL数据库全部采用InnoDB为搜索引擎InnoDB是面向在线事务处理的应用支持B树索引、哈希索引、全文索引等。但是InnoDB使用B树支持索引的实现方式与MyISAM却有着很大的不同。
InnoDB文件本身就是索引文件的一部分。在InnoDB的中B树的叶子节点要存放表的全部数据数据库中的数据要按照主键从小到大的顺序排列起来。如图5.3所示InnoDB的叶子节点中要包含所有的数据记录这种索引叫做聚集索引。由于InnoDB数据文件本身要按照主键来聚集因此InnoDB必须有主键而MyISAM则可以没有主键。 图5.3 InnoDB主键索引 InnoDB建立B树辅助索引叶子节点的数据域中记录的并不是数据数据文件本身的内容而是对应的主键如图5.4所示在InnoDB索引方式下建立对于name的辅助索引叶子结点数据域就存储了对应的StdId学号使用辅助索引检索时先拿到对应的主键再通过主索引查找内容这样就相当于要检索两次。 图5.4 InnoDB辅助索引 六. 总结
常见的搜索结构有哈希、二分、顺序查找、平衡二叉树等这些数据结构和算法都只适用于内查找。对于海量数据内存中无法容纳应当使用B树/B树来进行检索B/B树是高效的外查找专用数据结构。MySQL数据库的检索主要是通过B树来进行的有MyISAM和InnoDB两种检索方式MyISAM的B树的叶子节点的数据域中存储的是数据文件在磁盘中的地址InnoDB的B树的叶子节点中数据域存放的是数据文件本身。B树做外查找时B树本身存储在磁盘中。
