seo网站推广 沈阳,湖南哪里有做网站的,宝山网站推广,谷歌关键词搜索量数据查询目录
常见的搜索结构B-树概念B-树的插入分析B-树的插入实现B树和B*树B-树的应用 1. 常见的搜索结构
种类数据格式时间复杂度顺序查找无要求O(N)二分查找有序O( l o g 2 N log_2N log2N)二分搜索树无要求O(N)二叉平衡树无要求O( l o g 2 N log_2N log2N)哈希无要求O(1)
以…目录
常见的搜索结构B-树概念B-树的插入分析B-树的插入实现B树和B*树B-树的应用 1. 常见的搜索结构
种类数据格式时间复杂度顺序查找无要求O(N)二分查找有序O( l o g 2 N log_2N log2N)二分搜索树无要求O(N)二叉平衡树无要求O( l o g 2 N log_2N log2N)哈希无要求O(1)
以上结构适合用于数据量相对不是很大能够一次性存放在内存中进行数据查找的场景。如果数据量很大比如有100G数据无法一次放进内存中那就只能放在磁盘上了如果放在磁盘上有需要搜索某些数据那么如果处理呢那么我们可以考虑将存放关键字及其映射的数据的地址放到一个内存中的搜索树的节点中那么要访问数据时先取这个地址去磁盘访问数据。 使用平衡二叉搜索树的缺陷 平衡二叉搜索树的高度是logN这个查找次数在内存中时最快的。但是当数据都在磁盘中时访问磁盘速度很慢在数据量很大时logN次的磁盘访问是一个难以接受的结果
使用哈希表的缺陷 哈希表的效率很高是O(1)但是一些极端场景下某个位置冲突很多导致访问次数剧增
那如何加速对数据的访问 1.提高IO的速度SSD相比传统机械硬盘快了不少但是还没有得到本质性的提升 2.降低树的高度–多叉平衡树
2. B树概念
1970年R.Bayer和E.mccreight提出了一种适合外查找的树它是一种平衡的多叉树称为B树(后面有一个B的改进版本B树然后有些地方的B树写的的是B-树注意不要误读成B减树)。一棵m阶(m2)的B树是一棵平衡的M路平衡搜索树可以是空树或者满足一下性质
1.根节点至少有两个孩子 2.每个分支节点都包含k-1个关键字和k个孩子其中ceil(m/2) k mceil则是向上取整函数 3.每个叶子结点都包含k-1个关键字其中ceil(m/2) ≤ k ≤ m 4.所有的叶子节点都在同一层 5.每个节点中的关键字从小到大排列节点当中k-1个元素正好是k个孩子包含的元素的值域划分 6.每个节点的结构为{nA0K1A1K2A2.。。KnAn}其中K(1≤i≤n)位关键字且Ki Ki1 (1≤i≤n)为指向子树根节点的指针。且Ai所指子树所有节点中的关键字均小于Ki1 n为节点中关键字的个数满足ceil(m/2)-1≤n≤m-1
3. B-树的插入分析
为了简单起见假设M3即三叉树每个节点中存储两个数据两个数据可以将区间分割成三个部分因此节点应该有3个孩子节点结构如下: 注意孩子永远比数据多一个 用序列{53,139,75,49,145,36,101}构建B树的过程如下
3.1 结构设计
b树的节点用n记录已经保存的数据数量用数组保存关键字孩子数量比关键字多一个再用一个指针保存当前节点的父亲方便插入
template class K, size_t M
struct BTreeNode
{size_t _n; // 记录存储多少个关键字K _keys[M]; struct BTreeNodeK, M* _subs[M 1]; // 孩子struct BTreeNodeK, M* _parent; // 父亲BTreeNode(){for (size_t i 0; i M; i){_keys[i] K();_subs[i] nullptr;}_n 0;_subs[M] nullptr;_parent nullptr;}
};B树保存一个根节点
template class K, size_t M
class BTree
{typedef struct BTreeNodeK, M node;private:node* _root nullptr;
};3.2 查找
要实现插入先提供一个查找关键字存不存在的功能 两个循环内部循环用来在一个节点中查找如果key比当前值大key就如果小就跳到它的左子树。找到返回地址和下标找不到返回它的父节点方便插入
// 返回指针和节点中的位置
std::pairnode*, int 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]){i;}else if (key cur-_keys[i]){break;}else{return std::make_pair(cur, i);}}parent cur;// 往孩子跳cur cur-_subs[i];}return std::make_pair(parent, -1);
}插入过程总结
1.如果树为空直接插入新节点该结点为树的根节点 2.树非空找待插入元素在树中的插入位置注意找到的插入节点位置一定在叶子节点中 3.检测是否找到插入位置假设树中的key唯一即该元素已经存在不插入 4.按照插入排序的思想将该元素插入到找到的节点中 5.检测该结点是否满足B-树的性质即该节点中的元素个数是否等于M如果小于则满足 6.如果插入后节点不满足B树的性质需要对该节点分裂
申请新及诶点找到该节点的中间位置将该节点的中间位置右侧的元素以及孩子搬移到新节点中将中间位置元素以及新节点往该节点中的双亲节点中插入即继续
7.如果向上已经分裂到根节点的位置插入结束
4. B树的插入实现
分为两个部分一个函数用来找到插入位置插入一个函数进行后续的调整分裂保证B树特征
4.1 插入数据
插入的时候走的是插入的逻辑挪动数据的同时要挪动孩子插入成功还要连接父亲
// 找到节点中的插入位置插入数据
void InsertKey(node* cur, const K key, node* child)
{int end cur-_n - 1;while (end 0){if (key cur-_keys[end]){// 挪动key和它的右孩子cur-_keys[end 1] cur-_keys[end];cur-_subs[end 2] cur-_subs[end 1];end--;}else{break;}}cur-_keys[end 1] key;cur-_subs[end 2] child;// 第一次可能为空if (child){child-_parent cur;}cur-_n;
}4.2 调整
需要注意清空原数据和孩子和父亲的连接
// 插入的分裂等补充
bool Insert(const K key)
{if (_root nullptr){node* new_node new node;new_node-_keys[0] key;_root new_node;_root-_n;return true;}// key已经存在不允许插入std::pairnode*, int ret Find(key);node* parent ret.first;if (ret.second 0){return false;}// 如果没有找到find顺便带回了要插入的叶子节点// 循环每次往cur插入newkey和childK new_key key;node* child nullptr;while (1){InsertKey(parent, new_key, child);// 没满结束if (parent-_n M){return true;}// 满了分裂node* brother new node;size_t j 0;// 分裂一半[mid 1, M - 1]给兄弟size_t mid M / 2;size_t i mid 1;// 拷贝key还要拷贝孩子for (; i M; i){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;K mid_key parent-_keys[mid];parent-_keys[mid] K();// 说明刚刚分裂的是头节点if (parent-_parent nullptr){_root new node;_root-_keys[0] mid_key;_root-_subs[0] parent;_root-_subs[1] brother;_root-_n 1;parent-_parent _root;brother-_parent _root;return true;}else{// 转换成往parent-parent 去插入parent-[mid] 和 brothernew_key mid_key;child brother;parent parent-_parent;}}
}4.3 B-树的简单验证
对B树中序遍历如果得到一个有序的序列说明插入正确。和搜索二叉树类似先左再根再往右移动
void _Inorder(node* cur)
{if (cur nullptr){return;}// 左 根 左 根 。。。 右size_t i 0;for (; i cur-_n; i){_Inorder(cur-_subs[i]); // 左子树std::cout cur-_keys[i] ; // 根}// 最后的那个右子树_Inorder(cur-_subs[i]);
}void Inorder()
{_Inorder(_root);
}4.5 B-树的性能分析
对于一棵节点为N度为M的B-树查找和插入需要 l o g ( M − 1 ) N log(M-1)N log(M−1)N~ l o g ( M / 2 ) N log(M/2)N log(M/2)N次比较对于度为M的B-树每一个节点的子节点个数为M/2 ~ M-1之间因此树的高度应该在 l o g ( M − 1 ) N log(M-1)N log(M−1)N和 l o g ( M / 2 ) N log(M/2)N log(M/2)N之间在定位到该结点后再采用二分查找的方式可以很快的定位到该元素
B-树的效率是很高的对于N62*1000000000个节点如果度M为1024则 l o g M / 2 N log_{M/2}N logM/2N 4即在620亿个元素中如果这棵树的度为1024则需要小于4次即可定位到该结点然后利用二分查找可以快速定位到该元素大大减少了读取磁盘的次数
4.6 B-树的删除
学习B树的插入足够帮助理解B树的特性删除可以参考《算法导论》和《数据局结构-殷人昆》-C
5. B树和B*树
B树是B树的变形在B树基础上优化的多路平衡搜索树B树的规则跟B树基本类似但是又在B树的基础上做了以下几点改进优化
1.分支节点的子树指针与关键字个数相同相当于取消了最左的子树 2.分支节点的子树指针p[i]指向关键字值大小在[k[i]k[i1]]区间之间 3.所有叶子节点增加一个连接指针连接在一起 4.所有关键字及其映射数据都在叶子节点出现 B树的特性 1.所有关键字都出现在叶子结点的链表中且链表中的节点都是有序的 2.不可能在分支节点命中 3.分支节点相当于是叶子节点的索引叶子节点才是存储数据的
5.2 B树
B*树是B树的变形在B树中的非跟和非叶子点再增加指向兄弟节点的指针 B树的分裂 当一个节点满时分配一个新的节点并将原节点中1/2的数据复制到新节点最后在父节点中增加新及诶点的指针B树的分裂只影响原节点和父节点而不会影响兄弟节点所以它不需要指向兄弟的指针
B*树的分类 当一个结点满时如果它的下一个兄弟结点未满那么将一部分数据移到兄弟结点中再在原结点插入关键字最后修改父结点中兄弟结点的关键字因为兄弟结点的关键字范围改变了如果兄弟也满了则在原结点与兄弟结点之间增加新结点并各复制1/3的数据到新结点最后在父结点增加新结点的指针。所以B*树分配新结点的概率比B树要低空间使用率更高
5.3 总结
B树有序数组平衡多茶树 B树有序数组链表平衡多叉树 B*树一颗丰满的空间利用率更高的B树
内存查找B树没有优势 1.空间利用率低。消耗高 2.插入删除数据时分裂和合并节点必然挪动数据 3.虽然高度更低但是在内存而言和哈希和平衡搜索树还是一个量级
6. B树的应用
6.1 索引
B-树最常见的应用就是用来做索引。索引通俗的说就是为了方便用户快速找到所寻之物比如书籍目录可以让读者快速找到相关信息hao123网页导航网站为了让用户能够快速的找到有价值的分类网站本质上就是互联网页面中的索引结构。
MySQL官方对索引的定义为索引(index)是帮助MySQL高效获取数据的数据结构简单来说索引就是数据结构。
当数据量很大时为了能够方便管理数据提高数据查询的效率一般都会选择将数据保存到数据库因此数据库不仅仅是帮助用户管理数据而且数据库系统还维护着满足特定查找算法的数据结构这些数据结构以某种方式引用数据这样就可以在这些数据结构上实现高级查找算法该数据结构就是索引。
6.2 MySQL索引简介
mysql是目前非常流行的开源关系型数据库不仅是免费的可靠性高速度也比较快而且拥有灵活的插件式存储引擎 索引属于存储引擎级别的概念不同存储引擎对索引的实现方式不同 注意索引是基于表的而不是基于数据库的
6.2.1 MyISAM
MyISAM引擎是MySQL5.5.8版本之前默认的存储引擎不支持事物支持全文检索使用BTree作为索引结构叶节点的data域存放的是数据记录的地址其结构如下
上图是以以Col1为主键MyISAM的示意图可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中主索引和辅助索引Secondary key在结构上没有任何区别只是主索引要求key是唯一的而辅助索引的key可以重复。如果想在Col2上建立一个辅助索引则此索引的结构如下图所示 同样也是一棵BTreedata域保存数据记录的地址。因此MyISAM中索引检索的算法为首先按照BTree搜索算法搜索索引如果指定的Key存在则取出其data域的值然后以data域的值为地址读取相应数据记录。MyISAM的索引方式也叫做“非聚集索引”的。
6.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域。 聚簇索引这种实现方式使得主键的搜索十分高效但是辅助索引需要检索两变索引首先检索辅助索引获得主键然后用主键到主索引中检索获得记录如用id和名字分别查找
B树主键索引相比B树的优势 1.B树所有值都在叶子遍历很方便方便区间查找 2.对于没有建立索引的字段全表扫描的遍历也很方便 3.分支节点值存储key一个分支节点空间占用更小可以尽可能加载到内存
B树不用叶子就能找到值B树一定要到叶子。这是B树的优势但是B树高度足够低所以差别不大
参考资料 http://blog.codinglabs.org/articles/theory-of-mysql-index.html
