国内最专业的IT技术学习网

Mysql数据库

当前位置:主页 > Mysql数据库 >

银河官网:为什么MySQL索引要用B+树,而不是B树?

发布时间:2019/09/24标签:   mysql      InnoDB      B+树    点击量:

原标题:银河官网:为什么MySQL索引要用B+树,而不是B树?

information_schema.INNODB_SYS_TABLES b 

总结

最后回顾一道 MySQL 面试题:为什么 MySQL 的索引要使用 B+ 树而不是其他树形结构?比如 B 树?现在这个问题的复杂版本可以参考本文。

FROM 

InnoDB 的所有数据文件(后缀为 ibd 的文件),他的大小始终都是 16384(16K)的整数倍。

+------------------+-------+ 

 

那么回到我们开始的问题,通常一棵B+树可以存放多少行数据?

银河官网:为什么MySQL索引要用B+树,而不是B树?

lineitem 表的数据行数为 600 多万,B+ 树高度为 3,customer 表数据行数只有 15 万,B+ 树高度也为 3。

那么可以算出一棵高度为 2 的 B+ 树,能存放 1170*16=18720 条这样的数据记录。

银河官网:为什么MySQL索引要用B+树,而不是B树?

Oracle和MySQL的JDBC到底有多慢?

| innodb_page_size | 16384 | 

指针少的情况下要保存大量数据,只能增加树的高度,导致 IO 操作变多,查询性能变低。

所以人们想了一个办法,用 B+ 树的方式组织这些数据,如下图所示:

可以看出尽管数据量差异较大,这两个表树的高度都是 3。换句话说这两个表通过索引查询效率并没有太大差异,因为都只需要做 3 次 IO。

那么现在我们需要计算出非叶子节点能存放多少指针?其实这也很好算,我们假设主键 ID 为 bigint 类型,长度为 8 字节,而指针大小在 InnoDB 源码中设置为 6 字节,这样一共 14 字节。

其实每张表的根页位置在表空间文件中是固定的,即 page number=3 的页(这点我们下文还会进一步证明)。

 

银河官网:为什么MySQL索引要用B+树,而不是B树?

InnoDB 存储引擎的最小存储单元是页,页可以用于存放数据也可以用于存放键值+指针,在 B+ 树中叶子节点存放数据,非叶子节点存放键值+指针。

数据表中的数据都是存储在页中的,所以一个页中能存储多少行数据呢?假设一行数据的大小是 1K,那么一个页可以存放 16 行这样的数据。

版权信息Copyright © 银河官网 版权所有    ICP备案编号:鲁ICP备09013610号