数据库索引的原理,为什么要用 B+树,为什么不用二叉树?

简介: 数据库索引的原理,为什么要用 B+树,为什么不用二叉树?

可以从几个维度去看这个问题,查询是否够快,效率是否稳定,存储数据多少,以及查找磁盘次数,为什么不是二叉树,为什么不是平衡二叉树,为什么不是B树,而偏偏是B+树呢?

为什么不是一般二叉树?

如果二叉树特殊化为一个链表,相当于全表扫描。平衡二叉树相比于二叉查找树来说,查找效率更稳定,总体的查找速度也更快。

为什么不是平衡二叉树呢?

我们知道,在内存比在磁盘的数据,查询效率快得多。如果树这种数据结构作为索引,那我们每查找一次数据就需要从磁盘中读取一个节点,也就是我们说的一个磁盘块,但是平衡二叉树可是每个节点只存储一个键值和数据的,如果是B树,可以存储更多的节点数据,树的高度也会降低,因此读取磁盘的次数就降下来啦,查询效率就快啦。

那为什么不是B树而是B+树呢?
1)B+树非叶子节点上是不存储数据的,仅存储键值,而B树节点中不仅存储键值,也会存储数据。innodb中页的默认大小是16KB,如果不存储数据,那么就会存储更多的键值,相应的树的阶数(节点的子节点树)就会更大,树就会更矮更胖,如此一来我们查找数据进行磁盘的IO次数有会再次减少,数据查询的效率也会更快。

2)B+树索引的所有数据均存储在叶子节点,而且数据是按照顺序排列的,链表连着的。那么B+树使得范围查找,排序查找,分组查找以及去重查找变得异常简单。

相关文章
|
4天前
|
数据库 索引
如何优化数据库索引?
【8月更文挑战第14天】如何优化数据库索引?
17 4
|
4天前
|
缓存 NoSQL Redis
一天五道Java面试题----第九天(简述MySQL中索引类型对数据库的性能的影响--------->缓存雪崩、缓存穿透、缓存击穿)
这篇文章是关于Java面试中可能会遇到的五个问题,包括MySQL索引类型及其对数据库性能的影响、Redis的RDB和AOF持久化机制、Redis的过期键删除策略、Redis的单线程模型为何高效,以及缓存雪崩、缓存穿透和缓存击穿的概念及其解决方案。
|
18天前
|
存储 SQL 关系型数据库
(六)MySQL索引原理篇:深入数据库底层揭开索引机制的神秘面纱!
《索引原理篇》它现在终于来了!但对于索引原理及底层实现,相信大家多多少少都有了解过,毕竟这也是面试过程中出现次数较为频繁的一个技术点。在本文中就来一窥`MySQL`索引底层的神秘面纱!
|
20小时前
|
存储 安全 数据库
数据库的索引都有哪些类型?如何选择?
【8月更文挑战第17天】数据库的索引都有哪些类型?如何选择?
4 0
|
2天前
|
存储 NoSQL 关系型数据库
Web中的数据库:原理、应用与代码实现
Web中的数据库:原理、应用与代码实现
|
5天前
|
存储 安全 数据库
数据库系统原理课程设计
这篇文章是关于数据库系统原理课程设计的,主题为图书借阅管理系统,涵盖了系统需求分析、数据库设计(包括概念结构、逻辑结构、规范化、物理设计以及安全性和维护设计)、系统详细设计(视图、存储过程和触发器设计),以及安全性设计,并强调了设计仅供参考,鼓励自主学习。
|
12天前
|
缓存 关系型数据库 MySQL
MySQL调优秘籍曝光!从索引到事务,全方位解锁高可用秘诀,让你的数据库性能飞起来!
【8月更文挑战第6天】MySQL是顶级关系型数据库之一,其性能直接影响应用的高可用性与用户体验。本文聚焦MySQL的高性能调优,从索引设计到事务管理,逐一解析。介绍如何构建高效索引,如联合索引`CREATE INDEX idx_order_customer ON orders(order_id, customer_id);`,以及索引覆盖查询等技术。
33 0
|
5天前
|
存储 关系型数据库 MySQL
MySQL——数据库备份上传到阿里云OSS存储
MySQL——数据库备份上传到阿里云OSS存储
18 0
|
8天前
|
SQL 存储 关系型数据库
"MySQL增列必锁表?揭秘InnoDB在线DDL,让你的数据库操作飞一般,性能无忧!"
【8月更文挑战第11天】在数据库领域,MySQL凭借其稳定高效的表现深受开发者喜爱。对于是否会在给数据表添加列时锁表的问题,MySQL的行为受版本、存储引擎等因素影响。从5.6版起,InnoDB支持在线DDL,可在改动表结构时保持表的可访问性,避免长时间锁表。而MyISAM等则需锁表完成操作。例如,在使用InnoDB的表上运行`ALTER TABLE users ADD COLUMN email VARCHAR(255);`时,通常不会完全锁表。虽然在线DDL提高了灵活性,但复杂操作或大表变更仍可能暂时影响性能。因此,进行结构变更前应评估其影响并择机执行。
27 6
|
7天前
|
Oracle 关系型数据库 MySQL
Mysql和Oracle数据库死锁查看以及解决
【8月更文挑战第11天】本文介绍了解决MySQL与Oracle数据库死锁的方法。MySQL可通过`SHOW ENGINE INNODB STATUS`查看死锁详情,并自动回滚一个事务解除死锁;也可手动KILL事务。Oracle则通过查询V$LOCK与V$SESSION视图定位死锁,并用`ALTER SYSTEM KILL SESSION`命令终止相关会话。预防措施包括遵循ACID原则、优化索引及拆分大型事务。