做什么网站能吸引流量,电视网站免费大全,网站服务器问题,php网站开发招聘一、常见的搜索结构
适合做内查找#xff1a; 以上结构适合用于数据量相对不是很大#xff0c;能够一次性存放在内存中#xff0c;进行数据查找的场景。如果数据量很大#xff0c;比如有 100G 数据#xff0c;无法一次放进内存中#xff0c;那就只能放在磁盘上了。
如果…一、常见的搜索结构
适合做内查找 以上结构适合用于数据量相对不是很大能够一次性存放在内存中进行数据查找的场景。如果数据量很大比如有 100G 数据无法一次放进内存中那就只能放在磁盘上了。
如果放在磁盘上有需要搜索某些数据那么如果处理呢 那么我们可以考虑将存放关键字及其映射的数据的地址放到一个内存中的搜索树的节点中那么要访问数据时先取这个地址去磁盘访问数据。 适合做外查找B树系列 1、使用平衡二叉树搜索树的缺陷 平衡二叉树搜索树的高度是 logN这个查找次数在内存中是很快的。但是当数据都在磁盘中时访问磁盘速度很慢在数据量很大时logN 次的磁盘访问是一个难以接受的结果。 2、使用哈希表的缺陷 哈希表的效率很高是 O(1)但是一些极端场景下某个位置冲突很多导致访问次数剧增也是难以接受的。 那如何加速对数据的访问呢 提高 IO 的速度SSD 相比传统机械硬盘快了不少但是还是没有得到本质性的提升。降低树的高度 —— 多叉树平衡树。 在平衡搜索树的基础上找优化空间
压缩高度二叉变多叉。一个节点里面有多个关键字及映射的值。 二、B树 的概念
1970 年R.Bayer 和 E.mccreight 提出了一种适合外查找的树它是一种平衡的多叉树称为 B树后面有一个 B 的改进版本 B树有些地方的 B树写的是 B-树 注意 不要误读成 “B减树”。 一棵 m 阶m2的 B树是一棵平衡的 M 路平衡搜索树可以是空树或者满足以下性质 根节点至少有两个孩子。每个分支节点都包含 k-1 个关键字和 k 个孩子其中 ceil(m/2) ≤ k ≤ mceil 是向上取整函数。 每个叶子节点都包含 k-1 个关键字其中 ceil(m/2) ≤ k ≤ m。 所有的叶子节点都在同一层。 每个节点中的关键字从小到大排列节点当中 k-1 个元素正好是 k 个孩子包含的元素的值域划分。 每个结点的结构为 (n, A0, K1, A1, K2, A2, …, Kn, An )。其中Ki (1≤i≤n) 为关键字且 KiKi1 (1≤i≤n-1)。Ai (0≤i≤n) 为指向子树根结点的指针且 Ai 所指子树所有结点中的关键字均小于 Ki1。n 为结点中关键字的个数满足 ceil(m/2)-1≤n≤m-1。 三、B-树 的插入分析 为了简单起见假设 M3即三叉树。每个节点中存储两个数据两个数据可以将区间分割成三个部分因此节点应该有三个孩子为了后续实现简单期间节点的结构如下 注意孩子永远比数据多一个。 用序列 {53, 139, 75, 49, 145, 36, 101} 构建 B树的过程如下 天然平衡向右和向上生长根节点分裂增加一层。 新插入的节点一定是在叶子节点插入叶子节点没有孩子不影响关键字和孩子的关系。 叶子节点满了分裂出一个兄弟提取中位数向父亲插入一个值和一个孩子。 插入过程总结 如果树为空直接插入新节点中该节点为树的根节点。树非空找待插入元素在树中的插入位置注意找到的插入节点位置一定在叶子节点中。检测是否找到插入位置假设树中的 key 唯一即该元素已经存在时则不插入。按照插入排序的思想将该元素插入到找到的节点中。检测该节点是否满足 B-树的性质即该节点中的元素个数是否等于 M如果小于则满足。如果插入后节点不满足 B树的性质需要对该节点进行分裂申请新节点找到该节点的中间位置将该节点中间位置右侧的元素以及其孩子搬移到新节点中将中间位置元素以及新节点往该节点的双亲节点中插入即继续 4。如果向上已经分裂到根节点的位置插入结束。 四、B-树 的插入实现 1、B-树 的节点设计 // M叉树即一个节点最多有M个孩子M-1个数据域
templateclass K, size_t M
struct BTreeNode
{//K _keys[M - 1];//BTreeNodeK, M* _subs[M];// 为了方便插入以后再分裂多给一个空间K _keys[M]; // 存放元素BTreeNodeK, M* _subs[M1]; // 存放孩子节点注意孩子比数据多一个BTreeNodeK, M* _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;}
}; 2、插入 key 的过程 按照插入排序的思想插入 key。 void InsertKey(Node* node, const K key, Node* child)
{// 按照插入排序思想插入keyint 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--;}elsebreak;}// 插入key以及新分裂出的节点node-_keys[end 1] key;node-_subs[end 2] child;// 更新节点的双亲if (child)child-_parent node;node-_n;
} 注意在插入 key 的同时可能还要插入新分裂出来的节点。 3、B-树 的插入实现 bool Insert(const K key)
{// 如果树为空直接插入if (_root nullptr){_root new Node;_root-_keys[0] key;_root-_n;return true;}// key已经存在不插入pairNode*, int ret Find(key);if (ret.second 0){return false;}// 如果没有找到find顺便带回了要插入的那个叶子节点// 循环每次往cur插入newkey和childNode* parent ret.first;K newKey key;Node* child nullptr;while (1){// 将key插入到parent所指向的节点中InsertKey(parent, newKey, child);// 满了就要分裂没有满插入就结束if (parent-_n M){return true;}else{size_t mid M / 2;// 分裂一半[mid1, M-1]给兄弟Node* brother new Node;// 将中间位置右侧的元素以及孩子搬移到新节点中size_t j 0;size_t i mid 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节点的剩余数据个数parent-_n - (brother-_n 1);K midKey parent-_keys[mid];parent-_keys[mid] K();// 如果刚刚分裂是根节点需要重新申请一个新的根节点// 将中间位置数据以及分裂出的新节点插入到新的根节点中插入结束if (parent-_parent nullptr){_root new Node;_root-_keys[0] midKey;_root-_subs[0] parent;_root-_subs[1] brother;_root-_n 1;parent-_parent _root;brother-_parent _root;break;}else // 如果分裂的节点不是根节点将中间位置数据以及新分裂出的节点继续向parent的双亲中进行插入{// 转换成往parent-parent去插入parent-[mid]和brothernewKey midKey;child brother;parent parent-_parent;}}}return true;
} 4、B-树 的简单验证 对 B树 进行中序遍历如果能得到一个有序的序列说明插入正确。 void _InOrder(Node* cur)
{if (cur nullptr)return;// 左 根 左 根 ... 右size_t i 0;for ( ; i cur-_n; i){_InOrder(cur-_subs[i]); // 左子树cout cur-_keys[i] ; // 根}_InOrder(cur-_subs[i]); // 最后的那个右子树
} 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 次即可定位到该节点然后利用 二分查找可以快速定位到该元素大大减少了读取磁盘的次数。 五、B树 B*树 1、B树 B树 是 B树 的变形是在 B树 基础上优化的多路平衡搜索树B树 的规则跟 B树 基本类似但是又在 B树 的基础上做了以下几点改进优化 分支节点的子树指针与关键字个数相同。分支节点的子树指针 p[i] 指向关键字值大小在 [k[i]k[i1]) 区间之间。所有叶子节点增加一个链接指针链接在一起。所有关键字及其映射数据都在叶子节点出现。 分支节点跟叶子节点有重复的值分支节点村的是叶子节点的索引。 父亲中存的是孩子节点中的最小值做索引。 分支节点可以只存储 key那么分支节点比较小分支节点映射的磁盘数据块就可以尽快加载到 Cache。 叶子节点存 key/value。 1B树 的特性 所有关键字都出现在叶子节点的链表中且链表中的节点都是有序的。 不可能在分支节点中命中。 分支节点相当于是叶子节点的索引叶子节点才是存储数据的数据层。 B树 的插入过程跟 B树 基本是类似的细节区别在于第一次插入两层节点一层做分支一层做根。 后面一样往叶子节点去插入插入满了以后分裂一半给兄弟转换成往父亲插入一个 key 和一个孩子孩子就是兄弟key 是兄弟的第一个最小值得 key。 2总结 简化 B树 孩子比关键字多一个的规则变成相等。所有值都在叶子上方便遍历查找所有值。 2、B*树 B*树 是 B树 的变形在 B树 的非根和非叶子节点再增加指向兄弟节点的指针。 1B树的分裂 当一个结点满时分配一个新的结点并将原结点中 1/2 的数据复制到新结点最后在父结点中增加加新结点的指针。B树 的分裂只影响原结点和父结点而不会影响兄弟结点所以它不需要指向兄弟的指针。 2B*树的分裂 当一个结点满时如果它的下一个兄弟结点未满那么将一部分数据移到兄弟结点中再在原结点插入关键字最后修改父结点中兄弟结点的关键字因为兄弟结点的关键字范围改变了。如果兄弟也满了则在原结点与兄弟结点之间增加新结点并各复制 1/3 的数据到新结点最后在父结点增加新结点的指针。 所以B*树 分配新结点的概率比 B树 要低空间使用率更高。 3、总结 B树有序数组 平衡多叉树。B树有序数组链表 平衡多叉树。B*树一棵更丰满的空间利用率更高的 B树。 六、B-树 的应用 1、索引 B-树 最常见的应用就是用来做索引。索引通俗的说就是为了方便用户快速找到所寻之物比如书籍目录可以让读者快速找到相关信息hao123 网页导航网站为了让用户能够快速的找到有价值的分类网站本质上就是互联网页面中的索引结构。 MySQL 官方对索引的定义为索引index是帮助 MySQL 高效获取数据的数据结构简单来说索引就是数据结构。 当数据量很大时为了能够方便管理数据提高数据查询的效率一般都会选择将数据保存到数据库。因此数据库不仅仅是帮助用户管理数据而且数据库系统还维护着满足特定查找算法的数据结构这些数据结构以某种方式引用数据这样就可以在这些数据结构上实现高级查找算法该数据结构就是索引。 B树 做主键索引相比 B树 的优势 B树 所有的值都在其叶子节点上遍历方便方便区间查找。对于没有建立索引的字段全表扫描的遍历很方便。分支节点只存储 key一个分支节点的空间占用更小可以尽可能加载到缓存中。 B树 的优势不需要遍历到叶子节点就能找到值而 B树 一定要遍历到叶子节点。但是 B树 的高度足够低所以二者差别并不大。 2、MySQL 索引简介 mysql 是目前非常流行的开源关系型数据库不仅是免费的可靠性高速度也比较快而且拥有灵活的插件式存储引擎如下 MySQL 中索引属于存储引擎级别的概念不同存储引擎对索引的实现方式是不同的。 注意 索引是基于表的而不是基于数据库的。 1MyISAM MyISAM 引擎是 MySQL 5.5.8 版本之前默认的存储引擎不支持事务支持全文检索使用 BTree 作为索引结构叶节点的 data 域存放的是数据记录的地址方便索引树和主键树映射同样的数据其结构如下 建表的主键就是 B树 的 keyB树 的 value 事存储一行数据的磁盘地址。 分支节点也需要存到磁盘中因为数据量大的话内存是存不下的。分支节点中应该是一个磁盘地址但是分支节点理论应该尽量被缓存到 Cache。 上图是以 Col1 为主键MyISAM 的示意图可以看出 MyISAM 的索引文件仅仅保存数据记录的地址。在 MyISAM 中主索引和辅助索引Secondary key在结构上没有任何区别只是主索引要求 key 是唯一的而辅助索引的 key 可以重复。如果想在 Col2 上建立一个辅助索引则此索引的结构如下图所示 同样也是一棵 BTreedata 域保存数据记录的地址。因此MyISAM 中索引检索的算法为首先按照 BTree 搜索算法搜索索引如果指定的 Key 存在则取出其 data 域的值然后以 data 域的值为地址读取相应数据记录。MyISAM 的索引方式也叫做 “非聚集索引” 的。 2InnoDB 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 建立索引时索引树的叶子节点和主键树的叶子节点中的数据不一样没有办法进行直接映射。 第二个区别是 InnoDB 的辅助索引 data 域存储相应记录主键的值而不是地址所有辅助索引都引用主键作为 data 域。 聚集索引这种实现方式使得按主键的搜索十分高效但是辅助索引搜索需要检索两遍索引首先检索辅助索引获得主键然后用主键到主索引中检索获得记录。 参考资料【高阶数据结构】MySQL 索引背后的数据结构及算法原理-CSDN博客
