知识点整理（八）——mysql中的B+树

背景

关于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大小，如果数据占用很大，那相同层高的树能存储的数据就更少了。换一种说法，存储相同记录数需要更高的层高，更高的层高意味着更多的读取磁盘次数。自然也就降低了性能。

为什么联合索引左匹配？

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