专栏首页一个会写诗的程序员的博客为什么MySQL InnoDB 存储引擎要用B+树做索引,而不用B树?

为什么MySQL InnoDB 存储引擎要用B+树做索引,而不用B树?

为什么MySQL InnoDB 存储引擎 要用B+树做索引,而不用B树?

(1)B+树空间利用率更高,可减少I/O次数

一般来说,索引本身也很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储的磁盘上。这样的话,索引查找过程中就要产生磁盘I/O消耗。而因为B+树的内部节点只是作为索引使用,而不像B树那样每个节点都需要存储硬盘指针。也就是说:B+树中每个非叶节点没有指向某个关键字具体信息的指针,所以每一个节点可以存放更多的关键字数量,即一次性读入内存所需要查找的关键字也就越多,减少了I/O操作。

e.g.

假设磁盘中的一个盘块容纳16bytes,而一个关键字2bytes,一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内 部结点需要2个盘快。而B+ 树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候,B 树就比B+ 树多一次盘块查找时间(在磁盘中是盘片旋转的时间)。

(2)增删文件(节点)时,效率更高

因为B+树的叶子节点包含所有关键字,并以有序的链表结构存储,这样可很好提高增删效率,基于范围查询更好。

(3)B+树的查询效率更加稳定

因为B+树的每次查询过程中,都需要遍历从根节点到叶子节点的某条路径。所有关键字的查询路径长度相同,导致每一次查询的效率相当。

关于B 树与 B+树

B树

每个节点都存储key和data,所有节点组成这棵树,并且叶子节点指针为null。

B+树

只有叶子节点存储data,叶子节点包含了这棵树的所有键值,叶子节点不存储指针。

后来又在B+树上增加了顺序访问指针,也就是每个叶子节点增加一个指向相邻叶子节点的指针,这样一棵树成了数据库系统实现索引的首选数据结构。

小结:B树和B+树的区别

1)B树的每个结点都存储了key和data,B+树的data存储在叶子节点上。

节点不存储data,这样一个节点就可以存储更多的key。可以使得树更矮,所以IO操作次数更少。

2)树的所有叶结点构成一个有序链表,可以按照关键码排序的次序遍历全部记录

由于数据顺序排列并且相连,所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻,所以缓存命中性没有B+树好。

树高度越小,I/O次数越少。 为什么是B+树而不是B树呢,因为它内节点不存储data,这样一个节点就可以存储更多的key。

MyISAM和InnoDB存储引擎

在MySQL中,最常用的两个存储引擎是MyISAM和InnoDB,它们对索引的实现方式是不同的。

MyISAM

data存的是数据地址。索引是索引,数据是数据。索引放在XX.MYI文件中,数据放在XX.MYD文件中,所以也叫非聚集索引。

InnoDB引擎

data存的是数据本身。索引也是数据。数据和索引存在一个XX.IDB文件中,所以也叫聚集索引。

区别

了解了数据结构再看索引,一切都不费解了,只是顺着逻辑推而已。另加两种存储引擎的区别:

1、MyISAM是非事务安全的,而InnoDB是事务安全的

2、MyISAM锁的粒度是表级的,而InnoDB支持行级锁

3、MyISAM支持全文类型索引,而InnoDB不支持全文索引

4、MyISAM相对简单,效率上要优于InnoDB,小型应用可以考虑使用MyISAM

5、MyISAM表保存成文件形式,跨平台使用更加方便

6、MyISAM管理非事务表,提供高速存储和检索以及全文搜索能力,如果在应用中执行大量select操作可选择

7、InnoDB用于事务处理,具有ACID事务支持等特性,如果在应用中执行大量insert和update操作,可选择。

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!
本文分享自作者个人站点/博客:https://www.jianshu.com/u/c55c7a9c8de6复制
如有侵权,请联系 cloudcommunity@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • 为什么MySQL索引要用B+树,而不是B树?

    原文链接:https://www.cnblogs.com/leefreeman/p/8315844.html

    业余草
  • MySQL为什么用B+树,而不用B树?

    1.b+树只有叶子节点存数据 b树是每个节点都存数据 在相同数据量下b树的高度更高,所以查询效率更低

    全栈程序员站长
  • mysql 中的innoDB 引擎的B+树索引

    在优化慢接口的时候,遇到一个问题,在通过索引查询数据库表的时候根据时间区间去扫描表的时候,开始时间时表扫描的其实位置吗?或者说根据时间日期B+索引能一次性定位到...

    居士
  • 为什么MongoDB索引用B树,而Mysql用B+树?

    如果面试官问的是,为什么Mysql中Innodb的索引结构采取B+树?这个问题时,给自己留一条后路,不要把B树喷的一文不值。因为网上有些答案是说,B树不适合做文...

    week
  • 为什么Mongodb索引用B树,而Mysql用B+树?

    好久没写文章了,今天回来重操旧业。 今天讲的这个主题,是《面试官:谈谈你对mysql索引的认识》,里头提到的一个坑。

    Java3y
  • 为什么Mongodb索引用B树,而Mysql用B+树?

    好久没写文章了,今天回来重操旧业。 今天讲的这个主题,是《面试官:谈谈你对mysql索引的认识》,里头提到的一个坑。

    帅地
  • MySQL索引为什么要用B+树实现?

    在从一堆数据中查找指定的数据时,我们常用的数据结构是哈希表和二叉查找树,表本质上就是一堆数据的集合,所以MySQL数据库用了B+树和哈希表来实现索引

    Java识堂
  • MySQL为什么选择B+树存储索引

    如果上面的表,我们执行SQL语句 select * from table where Col2=89; 这样就会造成全表扫描,从第一行读取到倒数第二行,然后拿到...

    码农编程进阶笔记
  • 【面试现场】为什么MySQL数据库要用B+树存储索引?

    小史是一个应届生,虽然学的是电子专业,但是自己业余时间看了很多互联网与编程方面的书,一心想进BAT互联网公司。

    用户1260737
  • 【面试现场】为什么MySQL数据库要用B+树存储索引?

    小史是一个应届生,虽然学的是电子专业,但是自己业余时间看了很多互联网与编程方面的书,一心想进BAT互联网公司。

    Java3y
  • 【面试现场】为什么MySQL数据库要用B+树存储索引?

    小史是一个应届生,虽然学的是电子专业,但是自己业余时间看了很多互联网与编程方面的书,一心想进BAT互联网公司。

    帅地
  • 【面试现场】为什么 MySQL 数据库要用B+树存储索引?

    小史是一个应届生,虽然学的是电子专业,但是自己业余时间看了很多互联网与编程方面的书,一心想进BAT互联网公司。

    五分钟学算法
  • 为什么选择b+树作为存储引擎索引结构

    本文的内容主要以问答方式展开,层层递进分析、解决问题,本文涉及内容会围绕下面三个问题展开。在开始阅读本文内容前,大家不妨先尝试自己回答下面三个问题!

    jaydenwen123
  • Mysql为什么最终用B+树做索引?

    索引能极大的减少存储引擎需要扫描的数据量 索引可以把随机IO变成顺序IO(索引指向(左小右大)) 索引可以帮助我们在进行分组、排序等操作时,避免使用临时表

    名字是乱打的
  • MySQL:从B树到B+树到索引再到存储引擎,来说说

    > 公众号:[Java小咖秀](https://t.1yb.co/jwkk),网站:[javaxks.com](https://www.javaxks.com)

    Java小咖秀
  • 面试官:为什么 MySQL 的索引要使用 B+ 树,而不是其它树?比如 B 树?

    来源 | https://www.cnblogs.com/leefreeman/p/8315844.html

    五分钟学算法
  • Mysql的索引为什么使用B+树而不使用跳表?

    直接遍历这一行行数据,性能就是O(n),比较慢。为了加速查询,使用了B+树来做索引,将查询性能优化到了O(lg(n))。

    小白debug
  • 一分钟掌握MySQL的InnoDB引擎B+树索引

    MySQL的InnoDB索引结构采用B+树,B+树什么概念呢,二叉树大家都知道,我们都清楚随着叶子结点的不断增加,二叉树的高度不断增加,查找某一个节点耗时就会增...

    阿伟

扫码关注腾讯云开发者

领取腾讯云代金券