即刻搜索网站提交入口,深圳做网站的网络,本地wordpress数据,做义工的同城网站MySQL索引为什么是B树 索引是帮助MySQL高效获取数据的数据结构#xff0c;在数据之外#xff0c;数据库还维护着满足特定查找算法的数据结构B树#xff0c;这些数据结果以某种特定的方式引用数据#xff0c;这样就可以在这些数据结构上实现高级查找算法#xff0c;提升数据…MySQL索引为什么是B树 索引是帮助MySQL高效获取数据的数据结构在数据之外数据库还维护着满足特定查找算法的数据结构B树这些数据结果以某种特定的方式引用数据这样就可以在这些数据结构上实现高级查找算法提升数据的查找速度这种数据结构就是索引
如果此时有一个user表在它还未建立索引的时候如果想要查找age为35岁的用户
select * from user where age 35那么此时在user表中会逐个查找每一行直到查找到最后一行然后返回age为35的行
idnameusernameage1001张三zhangsan201002李四lisi181003王九wangjiu351004赵六zhaoliu221005王八wangba17
这样的查找无疑是非常耗时的当数据量非常庞大时全部检索整张表会消耗大量的时间和性能因此需要为数据建立合适的索引来提高查询的效率
那为什么MySQL采用的是B数呢而不是二叉树、红黑数呢
二叉树
二叉树在查找时使用的是二分查找算法查询效率得到了提高并且二叉树简单易实现当数据量较小时普通二叉树的性能已经能满足要求开销更小 #mermaid-svg-BKqbkT2PHYbCcM8N {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-BKqbkT2PHYbCcM8N .error-icon{fill:#552222;}#mermaid-svg-BKqbkT2PHYbCcM8N .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-BKqbkT2PHYbCcM8N .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-BKqbkT2PHYbCcM8N .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-BKqbkT2PHYbCcM8N .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-BKqbkT2PHYbCcM8N .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-BKqbkT2PHYbCcM8N .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-BKqbkT2PHYbCcM8N .marker{fill:#333333;stroke:#333333;}#mermaid-svg-BKqbkT2PHYbCcM8N .marker.cross{stroke:#333333;}#mermaid-svg-BKqbkT2PHYbCcM8N svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-BKqbkT2PHYbCcM8N .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-BKqbkT2PHYbCcM8N .cluster-label text{fill:#333;}#mermaid-svg-BKqbkT2PHYbCcM8N .cluster-label span{color:#333;}#mermaid-svg-BKqbkT2PHYbCcM8N .label text,#mermaid-svg-BKqbkT2PHYbCcM8N span{fill:#333;color:#333;}#mermaid-svg-BKqbkT2PHYbCcM8N .node rect,#mermaid-svg-BKqbkT2PHYbCcM8N .node circle,#mermaid-svg-BKqbkT2PHYbCcM8N .node ellipse,#mermaid-svg-BKqbkT2PHYbCcM8N .node polygon,#mermaid-svg-BKqbkT2PHYbCcM8N .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-BKqbkT2PHYbCcM8N .node .label{text-align:center;}#mermaid-svg-BKqbkT2PHYbCcM8N .node.clickable{cursor:pointer;}#mermaid-svg-BKqbkT2PHYbCcM8N .arrowheadPath{fill:#333333;}#mermaid-svg-BKqbkT2PHYbCcM8N .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-BKqbkT2PHYbCcM8N .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-BKqbkT2PHYbCcM8N .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-BKqbkT2PHYbCcM8N .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-BKqbkT2PHYbCcM8N .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-BKqbkT2PHYbCcM8N .cluster text{fill:#333;}#mermaid-svg-BKqbkT2PHYbCcM8N .cluster span{color:#333;}#mermaid-svg-BKqbkT2PHYbCcM8N div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-BKqbkT2PHYbCcM8N :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;}#mermaid-svg-BKqbkT2PHYbCcM8N .circle*{fill:#ffffff!important;stroke:#000000!important;stroke-width:2!important;}#mermaid-svg-BKqbkT2PHYbCcM8N .circle span{fill:#ffffff!important;stroke:#000000!important;stroke-width:2!important;} 38 22 45 15 31 40 49 但是二叉树有一个非常致命的缺点高度不稳定
普通二叉树在数据分布不均时可能变成链表状最坏情况下高度为 O(n)影响查找性能 #mermaid-svg-sCnTlpLOEjaHoEz7 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-sCnTlpLOEjaHoEz7 .error-icon{fill:#552222;}#mermaid-svg-sCnTlpLOEjaHoEz7 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-sCnTlpLOEjaHoEz7 .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-sCnTlpLOEjaHoEz7 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-sCnTlpLOEjaHoEz7 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-sCnTlpLOEjaHoEz7 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-sCnTlpLOEjaHoEz7 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-sCnTlpLOEjaHoEz7 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-sCnTlpLOEjaHoEz7 .marker.cross{stroke:#333333;}#mermaid-svg-sCnTlpLOEjaHoEz7 svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-sCnTlpLOEjaHoEz7 .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-sCnTlpLOEjaHoEz7 .cluster-label text{fill:#333;}#mermaid-svg-sCnTlpLOEjaHoEz7 .cluster-label span{color:#333;}#mermaid-svg-sCnTlpLOEjaHoEz7 .label text,#mermaid-svg-sCnTlpLOEjaHoEz7 span{fill:#333;color:#333;}#mermaid-svg-sCnTlpLOEjaHoEz7 .node rect,#mermaid-svg-sCnTlpLOEjaHoEz7 .node circle,#mermaid-svg-sCnTlpLOEjaHoEz7 .node ellipse,#mermaid-svg-sCnTlpLOEjaHoEz7 .node polygon,#mermaid-svg-sCnTlpLOEjaHoEz7 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-sCnTlpLOEjaHoEz7 .node .label{text-align:center;}#mermaid-svg-sCnTlpLOEjaHoEz7 .node.clickable{cursor:pointer;}#mermaid-svg-sCnTlpLOEjaHoEz7 .arrowheadPath{fill:#333333;}#mermaid-svg-sCnTlpLOEjaHoEz7 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-sCnTlpLOEjaHoEz7 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-sCnTlpLOEjaHoEz7 .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-sCnTlpLOEjaHoEz7 .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-sCnTlpLOEjaHoEz7 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-sCnTlpLOEjaHoEz7 .cluster text{fill:#333;}#mermaid-svg-sCnTlpLOEjaHoEz7 .cluster span{color:#333;}#mermaid-svg-sCnTlpLOEjaHoEz7 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-sCnTlpLOEjaHoEz7 :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;}#mermaid-svg-sCnTlpLOEjaHoEz7 .circle*{fill:#ffffff!important;stroke:#000000!important;stroke-width:2!important;}#mermaid-svg-sCnTlpLOEjaHoEz7 .circle span{fill:#ffffff!important;stroke:#000000!important;stroke-width:2!important;} 38 22 20 15 红黑树
红黑树是一种自平衡二叉搜索树保证任何路径的最大深度不超过最小深度的两倍自平衡的特性完美解决了二叉树中高度不稳定的特点查找、插入和删除操作的时间复杂度始终保持在 O(logn)在插入和删除操作引入了旋转、变色等机制确保平衡性无需频繁重构树结构
红黑规则 每个节点都有一个颜色属性可以是红色或黑色。 红黑树的根节点必须是黑色。 所有的叶子节点即树中的 null 节点是黑色的。叶子节点不包含数据只是辅助结构。 如果一个节点是红色的则其子节点必须是黑色。这确保了没有两个红色节点相连从而避免了树的高度过高。 任何路径从根节点到叶子节点或者空节点的过程中必须经过相同数量的黑色节点。这保证了红黑树的平衡性避免了一些路径比其他路径过长从而影响查找效率。 #mermaid-svg-1Qvbg6lHWuHZejbP {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-1Qvbg6lHWuHZejbP .error-icon{fill:#552222;}#mermaid-svg-1Qvbg6lHWuHZejbP .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-1Qvbg6lHWuHZejbP .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-1Qvbg6lHWuHZejbP .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-1Qvbg6lHWuHZejbP .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-1Qvbg6lHWuHZejbP .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-1Qvbg6lHWuHZejbP .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-1Qvbg6lHWuHZejbP .marker{fill:#333333;stroke:#333333;}#mermaid-svg-1Qvbg6lHWuHZejbP .marker.cross{stroke:#333333;}#mermaid-svg-1Qvbg6lHWuHZejbP svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-1Qvbg6lHWuHZejbP .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-1Qvbg6lHWuHZejbP .cluster-label text{fill:#333;}#mermaid-svg-1Qvbg6lHWuHZejbP .cluster-label span{color:#333;}#mermaid-svg-1Qvbg6lHWuHZejbP .label text,#mermaid-svg-1Qvbg6lHWuHZejbP span{fill:#333;color:#333;}#mermaid-svg-1Qvbg6lHWuHZejbP .node rect,#mermaid-svg-1Qvbg6lHWuHZejbP .node circle,#mermaid-svg-1Qvbg6lHWuHZejbP .node ellipse,#mermaid-svg-1Qvbg6lHWuHZejbP .node polygon,#mermaid-svg-1Qvbg6lHWuHZejbP .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-1Qvbg6lHWuHZejbP .node .label{text-align:center;}#mermaid-svg-1Qvbg6lHWuHZejbP .node.clickable{cursor:pointer;}#mermaid-svg-1Qvbg6lHWuHZejbP .arrowheadPath{fill:#333333;}#mermaid-svg-1Qvbg6lHWuHZejbP .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-1Qvbg6lHWuHZejbP .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-1Qvbg6lHWuHZejbP .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-1Qvbg6lHWuHZejbP .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-1Qvbg6lHWuHZejbP .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-1Qvbg6lHWuHZejbP .cluster text{fill:#333;}#mermaid-svg-1Qvbg6lHWuHZejbP .cluster span{color:#333;}#mermaid-svg-1Qvbg6lHWuHZejbP div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-1Qvbg6lHWuHZejbP :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;}#mermaid-svg-1Qvbg6lHWuHZejbP .red*{fill:#ffaaaa!important;stroke:#000!important;stroke-width:2!important;color:#000!important;}#mermaid-svg-1Qvbg6lHWuHZejbP .red span{fill:#ffaaaa!important;stroke:#000!important;stroke-width:2!important;color:#000!important;}#mermaid-svg-1Qvbg6lHWuHZejbP .black*{fill:#000000!important;stroke:#fff!important;stroke-width:2!important;color:#fff!important;shape:circle!important;}#mermaid-svg-1Qvbg6lHWuHZejbP .black span{fill:#000000!important;stroke:#fff!important;stroke-width:2!important;color:#fff!important;shape:circle!important;} 50 30 70 20 40 60 80 17 但是当数据规模量巨大时他也会暴露出来缺点深度较大
因此红黑数无法适应大规模数据而且每个节点只存储一个键值导致树的层数增加浪费存储空间红黑树需要通过中序遍历才能完成范围查询因此在大规模数据量的场景下查询效率依然不高 B树
B树B-tree是一种自平衡的多路搜索树它能够保持数据有序并允许高效的插入、删除和查找操作
B树的特点包括
平衡性B树是一种平衡树所有叶子节点的深度相同。通过这种结构B树保证了对所有节点的访问时间是相同的从而提高了查找效率。多路性B树的每个节点可以有多个子节点通常是 m 个子节点。这使得B树能够存储更多的数据并且能更快地完成查找、插入、删除等操作。节点结构每个节点包含若干个关键字data并且包含指向其子节点的指针。对于每个节点中的关键字子节点的关键字范围是有序的。查找效率B树的查找操作类似于二叉查找树但是每个节点具有多个子节点。查找操作的时间复杂度为O(log n)其中n是树中的元素个数。插入和删除操作插入和删除操作需要保证树的平衡性插入时可能会导致节点分裂删除时可能会引起节点合并或借用关键字。所有这些操作都在O(log n)时间内完成。 他的单个节点可以存储多个数据和多个指针每个节点也可以有多个分支因此他的每一层级可以存放大量数据同样遵循左边大右边小的存储规则因此B树的查找效率是十分优秀的B树通常用于数据库和文件系统中用于存储和管理大量数据
但是MySQL中使用的数据结构并不是B树而是B树相比B树B树更加优秀 B树
B树是B树的变种它具有与B树类似的结构和特点但在某些方面有所改进特别是在存储和查找效率上。B树通常用于数据库和文件系统中作为一种高效的索引结构
所有数据都存储在叶子节点中 在B树中数据可以存储在内部节点和叶子节点中而在B树中所有的数据即关键字都仅存储在叶子节点中。内部节点只存储关键字用于引导查找过程。这种设计可以减少内部节点的存储空间提高查询效率。 叶子节点通过链表连接 B树的叶子节点通常是通过一个链表连接起来的这使得范围查询例如查找某个区间内的所有数据变得更加高效。通过遍历链表可以一次性返回区间内的所有数据而不需要回溯到其他节点。 树的高度较小 由于所有数据都存储在叶子节点中B树的内部节点只需要存储关键字和指向子节点的指针。因此相比于B树B树可以将更多的数据存储在每个节点中从而使树的高度变得更小查找操作的效率更高。 查找操作的效率更高 B树的查找操作通常仅限于叶子节点而B树在查找时可能需要在内部节点和叶子节点之间反复跳转。由于叶子节点之间有链表连接B树在范围查询时特别高效。 B树相较于B树在查找和范围查询上有显著的优势尤其在数据库和文件系统中因为它能够有效地减少磁盘I/O操作并提高查询效率。因此MySQL选择了B树作为索引的数据结构
