搭建网站的免费程序,知识库管理系统功能,app找什么公司,网页设计尺寸比例目录 MySQL 为什么使用 B 树来做索引#xff0c;它的优势是什么#xff1f;特性和定义B 树和 B 树的对比拓展#xff1a;既然 B 树相较于 B 树优势如此之大#xff0c;为什么 nosql 的 MongoDB 底层仍采用 B 树而不是 B 树#xff1f; 使用 B 树做索引的优势补充#xff… 目录 MySQL 为什么使用 B 树来做索引它的优势是什么特性和定义B 树和 B 树的对比拓展既然 B 树相较于 B 树优势如此之大为什么 nosql 的 MongoDB 底层仍采用 B 树而不是 B 树 使用 B 树做索引的优势补充为什么说 B 树的插入和删除效率高B 树的冗余结点是如何形成的它们的作用是什么冗余结点是如何帮助提高插入和删除效率的冗余结点指的是叶子节点冗余还是用做索引的非叶子节点冗余为什么说 B 树的插入和删除效率高结构特性带来的效率优势冗余节点的形成与作用冗余结点提升效率的原理冗余结点指的是叶子节点冗余还是用做索引的非叶子节点冗余冗余结点的本质 与其它数据结构的对比 索引有哪些种单值索引唯一索引主键索引复合索引前缀索引 什么是最左匹配原则拓展最左匹配原则是数据库索引设计的核心概念之一主要针对联合查询 索引区分度联合索引如何进行排序 MySQL 为什么使用 B 树来做索引它的优势是什么
特性和定义
B Tree 是一种多叉树叶子节点才存放具体的数据而非叶子节点仅存放索引每个结点当中的数据是按主键顺序存放的。在叶子节点中包括了所有的索引值信息并且每一个叶子节点都指向下一个叶子节点形成一个链表因此 B 树支持范围查询。B Tree 存储千万级别的数据只需要 3 ~ 4 层高度就可以满足加入一个非叶子结点存储 1000 个索引那么三层树高的情况下可以存储 100 0 3 1000000000 1000^3 1000000000 100031000000000十亿条数据千万级的表查询最多只需要 3 ~ 4 次磁盘 I/O。
B 树和 B 树的对比 数据存储分布 B 树所有结点均存储数据键值对 B 树仅叶子节点存储完整数据内部节点仅做索引键 指针 叶子节点结构 B 树独立叶子节点 B 树叶子节点通过双向链表串联形成有序链表结构 查询性能对比 B 树和 B 树的单点查询平均时间复杂度相当均为 O ( log d N ) O(\log_d{N}) O(logdN) 在进行范围查询时B 树通过链表直接进行顺序查询而 B 树则需要中序遍历效率差 10 倍。 空间利用率 B 树内部可以存储更多的键值树高普遍比 B 树低 2 层。 插入删除操作 B 树数据变更仅影响叶子节点而 B 树可能引发连锁节点的分裂与合并 典型应用场景 B 树MongoDB文档型数据库、文件系统 B 树MySQLInnoDB、Oracle、PostgreSQL 等关系型数据库 工程实践差异 B 树叶子节点存储密度可达 70%而 B 树通常为 50% ~ 60% 在处理百万级数据时B 树比 B 树减少 30% ~ 50% 的磁盘 I/O 次数得益于 B 树的高扇出与低树高特性 在进行范围查询时B 树比 B 树的性能高 5 ~ 10 倍得益于 B 树叶子节点之间的顺序连接特性。
拓展既然 B 树相较于 B 树优势如此之大为什么 nosql 的 MongoDB 底层仍采用 B 树而不是 B 树
B 树在关系型数据库如 MySQL中表现卓越因其擅长范围查询和排序而 MongoDB 作为文档数据库优先优化点查询和文档快速获取B 树的结构特性更契合其设计目标。
使用 B 树做索引的优势
单点查询B 树进行单个索引查询时最快可以在 O ( 1 ) O(1) O(1)的时间代价内完成因为 B 树当中的结点包括非叶子节点既存储索引又存储数据。从平均时间代价上来看它比 B 树更快。但是 B 树的查询波动比较大原因同样是每个节点既存储索引又存储数据所以有时候访问到非叶子节点即可找到索引有时候需要访问到叶子节点才能找到索引。B 树的非叶子节点不存放实际的记录数据而只存放索引在数据量相同的情况下B 树的非叶子节点可以存放更多的索引查询底层结点的 I/O 更少因此 B 树在做单点查询时更加稳定。插入和删除效率B 树含有大量的冗余结点删除一个节点时可以直接从叶子结点删除甚至可以不动非叶子节点删除非常快。B 树的插入也是一样有冗余结点插入可能存在结点的分裂如果节点饱和但是最多只涉及树的一条路径。B 树没有冗余结点删除节点非常复杂可能涉及复杂的树的变形。范围查询B 树的所有叶子节点直接通过双向链表连接而 B 树没有将叶子节点通过链表串联因此 B 树只能通过树的遍历来完成范围查询其范围查询的效率不如 B 树。B 树的插入删除效率非常高当面对存在大量的范围检索的场景时适合使用 B 树比如数据库而对于存在大量单个索引查询的场景可以考虑 B 树比如 nosql 的 MongoDB。
补充为什么说 B 树的插入和删除效率高B 树的冗余结点是如何形成的它们的作用是什么冗余结点是如何帮助提高插入和删除效率的冗余结点指的是叶子节点冗余还是用做索引的非叶子节点冗余
为什么说 B 树的插入和删除效率高结构特性带来的效率优势
多路平衡特性每个结点可存储大量键值高扇出树高通常维持在 3 ~ 4 层磁盘 I/O 次数更少顺序访问优化叶子节点之间形成有序链表InnoDB 在实现上使用双向链表范围查询效率极高写操作局部性插入/删除只需要修改局部节点具体来说指的就是叶子节点多数情况下不会引发连锁结构调整。
冗余节点的形成与作用
冗余节点类型主要存在于非叶子节点即索引节点形成机制插入时结点分裂会产生临时性父节点键值冗余删除节点时合并会暂时保留未及时清理的索引键批量操作时会延迟维护产生的中间状态作用缓冲结构调整压力避免频繁的节点分裂/合并允许临时超出结点容量限制为并发操作提供版本控制的可能性。
冗余结点提升效率的原理
延迟维护非叶子节点的冗余键允许暂时不立即处理结构变更批量处理多个操作累积后一次性处理冗余摊平维护成本概率优化利用节点填充因子如 70% 阈值预留空间缓冲突发操作。
冗余结点指的是叶子节点冗余还是用做索引的非叶子节点冗余冗余结点的本质
冗余结点是 B 树用空间换时间的典型设计通过允许非叶子节点存在临时性的冗余键值换取更平缓的结构维护代价。叶子节点由于需要保证数据的有序性冗余主要表现为预留空间而非键值重复。
与其它数据结构的对比
B 树对比 B 树B 树只在叶子节点存储数据而 B 树的非叶子节点也存储数据。因此 B 树的单个结点数据量更小在数据量相同的前提下B 树可以存储更多的索引在相同的磁盘 I/O 次数下B 树可以查询更多的结点。B 树的叶子节点采用双向链表连接具体来说MySQL 的 InnoDB 在实现细节上是采用双向链表的。早期 MySQL 的 MyISAM 引擎使用单向链表InnoDB 自 MySQL 5.5 称为默认引擎后叶子节点之间的双向链表连接称为标准实现适合 MySQL 中常见的基于范围的查询而 B 树做不到这一点因此它更适用于单点查询。B 树对比二叉树对于有 N 个叶子节点的 B 树其搜索复杂度为 O ( log d N ) O(\log_d{N}) O(logdN)其中 d 表示结点允许的最大子节点个数。实际应用中d 值大于 100即使数据达到千万级B Tree 的高度依然维持在 3 ~ 4 层一次查询只需要 3 ~ 4 次磁盘 I/O 就能查到。二叉树每个父节点的儿子结点个数为 2 个意味着其搜索复杂度为 P ( log N ) P(\log{N}) P(logN)二叉树搜索到目标数据需要的磁盘 I/O 数更多。B 树对比哈希哈希在做等值查询时效率较高搜索复杂度为 O ( 1 ) O(1) O(1)但是 Hash 不适合做范围查询。
索引有哪些种
单值索引
单值索引即一个索引只包含单个列一个表可以有多个单列索引。
建表时加上 key(列名) 指定单独创建create index 索引吗 on 表名(列名)单独创建alter table 表名 add index 索引名(列名)
唯一索引
唯一索引中索引列的值必须唯一但允许有 null 且 null 可以多次出现。
建表时加上 unique(列名) 指定单独创建create unique index idx 表名(列名) on 表名(列名)单独创建alter table 表名 add unique 索引名(列名)
主键索引
设定为主键后数据库会自动建立索引InnoDB 为聚簇索引值必须唯一且不能为 null。
建表时加上 primary key(列名) 指定
复合索引
复合索引即一个索引包含多个列。
建表时加上 key(列名列表) 指定单独创建create index 索引名 on 表名(列名列表)单独创建alter table 表名 add index 索引名(列名列表)
前缀索引
对字符类型字段的前几个字符建立的索引而不是在整个字段上建立的索引前缀索引可以建立在字段类型为 char、 varchar、binary、varbinary 的列上。使用前缀索引的目的是为了减少索引占用的存储空间提升查询效率。
单独创建alter table 表名 add 索引名(column_name(索引长度))。
什么是最左匹配原则
使用联合索引时存在最左匹配原则也就是按照最左优先的方式进行索引的匹配。使用联合索引进行查询的时候如果不遵循最左匹配原则联合索引会失效。
拓展最左匹配原则是数据库索引设计的核心概念之一主要针对联合查询
最左匹配原则规定了在使用联合索引时查询条件必须从索引定义的最左侧列开始不能跳过中间的列这样才能有效地利用索引进行快速检索。
联合索引按照定义时的列顺序构建 B 树结构例如索引(a, b, c)数据先按a排a相同再按b排b相同按c排。
联合索引的生效条件是查询必须包含最左列条件列需要连续无跳跃。若某列使用范围查询则其右侧的列无法继续使用索引比如WHERE a1 AND b10 AND c2仅a和b有效c需回表过滤。
案例 WHERE a1 AND b2 AND c3 -- ✅ 使用a、bc因b范围查询失效 WHERE b2 -- ❌ 缺少最左列a WHERE a1 AND c3 -- ❌ 跳过b仅用ac无法走索引 WHERE a1 AND b2 -- ❌ a范围查询后b无法走索引失效原因当a使用范围查询时b的等值条件无法有效利用索引数据库只能使用a1的索引范围扫描此时b2的记录在索引中是离散分布的
索引区分度
查询优化器在发现某个值出现在表的数据行中的百分比惯用的百分比界限为 30%很高时会忽略索引进行全表扫描。
联合索引如何进行排序
以(a, b, c)为例第一优先级按 a 列值升序排序第二优先级a 相同则按 b 列值升序排序第三优先级a 和 b 都相同按 c 值升序排序。
排序特性
局部有序性每个 a 值的范围内b 是有序的每个 a, b 组合内c 是有序的。跨级断点a 改变时b 和 c 的排序重新开始。
对查询的影响
范围查询会破坏后续列的排序优势如a1时b的排列不再全局有序等值查询能保持后续列的排序如a1时b仍保持升序排列
