加载中...
知识点整理(八)——mysql中的B+树
发表于:2021-09-14 | 分类: 程序人生
字数统计: 972 | 阅读时长: 3分钟 | 阅读量:

背景

关于mysql的B+树,经常会遇到有关的这么几个问题:

  1. B+树索引是什么?
  2. 为什么B+树(比B树)更适合做数据库索引?
  3. 为什么B+树索引一页是16k?
  4. 为什么建议主键自增?
  5. 为什么不建议存储text等大类型?或者建议拆分表来存储?
  6. 为什么联合索引左匹配?

正文

B+树索引是什么?

B+树需要满足以下几个要求:

  1. 从根节点到叶节点的所有路径都具有相同的长度。
  2. 所有数据信息存储在叶子节点,非叶子节点仅作为叶子节点的索引存在。
  3. 根节点至少拥有2个子树。
  4. 每个树节点最多拥有M个子树
  5. 每个节点(除了根节点)拥有至少M/2个子树。

为什么B+树更适合做数据库索引?

  • B+树层高比较低,在搜索时能够减少磁盘读取次数。
  • B+树(聚簇索引)数据存储在叶子节点,搜索完成的时候就能一次取出所有数据,避免额外磁盘读取。(磁盘预读)
  • B+树非叶子节点仅存储索引数据,大大减小数据量,可以一次读取到内存中(单个节点)。
  • B+树索引在叶子节点存在双向链表,可以支持范围查询、扫表。

为什么B+树索引一页是16k?

从磁盘的物理结构来看存取信息的最小单位是扇区,一个扇区是512字节。
从操作系统对硬盘的存取管理来看,存取信息的最小单位是簇,簇是一个逻辑概念,一个簇可以是2、4、8、16、32或64个连续的扇区。NTFS文件系统格式化的时候默认是8个扇区组成一个簇,即4096字节。linux的分区常用的也是4K大小。

对于系统来说,一次磁盘读取最小读取4K数据,那么如果程序只需要1.5K,5.5K数据都会是浪费。所以索引的一页一般是4K的倍数,默认是16K。

那为什么是16K而不是4K 8K呢?原因是16K在大多数场景下够用了。

我们假设一条记录大小1K左右,那一页(叶子节点)能够存储16条记录。如果表的主键是bigint,也就是8B,指针大小在innodb中为6B,也就是14B。一页(非叶子节点)能够存储16K/14=1170个。那一个高度为2的B+树可以存储117016 = 18720条记录 ,一个高度为3的B+树可以存储11701170*16=21902400条记录,大概是2千万左右。这个量一般都是够用了。

为什么建议主键自增?

因为B+树的聚簇索引在非叶子节点上都是顺序排列的,紧凑自增的key能够减少树的分裂。

为什么不建议存储text等大类型?或者建议拆分表来存储?

可以看到上面我们计算一个层高为3的B+树可以存储多少数据时有1个假设,那就是一条记录占用1K大小,如果数据占用很大,那相同层高的树能存储的数据就更少了。换一种说法,存储相同记录数需要更高的层高,更高的层高意味着更多的读取磁盘次数。自然也就降低了性能。

为什么联合索引左匹配?

联合索引和会把所有索引字段写入节点,但是是按照第一个索引、第二个索引、第三个索引的顺序排列的。这就导致优先从第一个索引处过滤查找,如果第一个索引不能确定,或者不是连续的,那就无法立刻定位第二个索引的范围了。

上一篇:
知识点整理(九)——mysql的MVCC
下一篇:
知识点整理(七)——java中的AQS
本文目录
本文目录