解读MySQL中一个B+树能存储多少数据

MySQL中一个B+树能存储多少数据

MySQL聚簇索引的存储结构

MySQL中InnoDB页的大小默认是16k。也可以自己进行设置。（计算机在存储数据的时候，最小存储单元是扇区，一个扇区的大小是 512 字节，而文件系统（例如 XFS/EXT4）最小单元是块，一个块的大小是 4KB。

InnoDB 引擎存储数据的时候，是以页为单位的，每个数据页的大小默认是 16KB，即四个块。）

在B+树中，一个结点就是一页。非叶子结点由主键值和一个指向下一层的地址的指针组成的组合组成。叶子结点中由一组键值对和一个指向该层下一页的指针组成，键值对存储的主键值和数据。

由存储结构，可以大概计算出一个B+树能存储的数据数量。

指针在InnoDB中为6字节，设主键的类型是bigint，占8字节。一组就是14字节。

计算出一个非叶子结点可以存储16 * 1024 / 14 = 1170个索引指针。

假设一条数据的大小是1KB，那么一个叶子结点可以存储16条数据。

得出两层B+树可以存储1170 x 16 = 18720 条数据。

三层B+树可以存储1170 x 1170 x 16 = 21902400条数据。

MySQL中B树与B+树的区别

B树

B树和B+树都是应用在数据库索引上，可以认为是m叉的多路平衡查找树，但是理论上讲，二叉树的查找速度和比较次数都更小，为什么不用二叉树呢？

这是因为我们要考虑磁盘IO的影响，它相对于内存来说是很慢的，数据库索引是存储在磁盘上的，当数据量很大时，就不能把整个索引全部加载到内存中，只能逐一加载每一个磁盘页（对应索引树的节点）。

所以我们要减少IO的次数，对于树来说，IO次数就是树的高度，而“矮胖”就是B树的特征之一。

B树的特征：

• 关键字集合分布在整颗树中；
• 任何一个关键字出现且只出现在一个结点中；
• 搜索有可能在非叶子结点结束；
• 其搜索性能等价于在关键字全集内做一次二分查找；

B+树

B+树是B树的变体，是一种查询性能更好的B树。B+树是一种平衡查找树。在B+树中，所有记录节点都是按键值的大小顺序存放在同一层的叶节点中，各叶结点指针进行连接。

B+树的特征：

• 有n棵子树的非叶子结点中含有n个关键字（b树是n-1个），这些关键字不保存数据，只用来索引，所有数据都保存在叶子节点（b树是每个关键字都保存数据）。
• 所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
• 所有的非叶子结点可以看成是索引部分，结点中仅含其子树中的最大（或最小）关键字。
• 通常在b+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。
• 同一个数字会在不同节点中重复出现，根节点的最大元素就是b+树的最大元素。

B树与B+树的区别

• B树的中间节点保存节点和数据，B+树的中间节点不保存数据，数据保存在叶子节点中；所以磁盘页能容纳更多的节点元素，更“矮胖”；
• B树的查找要只要匹配到元素，就不用管在什么位置，B+树查找必须匹配到叶子节点，所以B+树查找更稳定；
• 对于范围查找到说，B树要从头到尾查找，而B+树只需要在一定的范围内的叶子节点中查找就可以；
• B+树的叶子节点通过指针连接，从左到右顺序排列；
• B+树的非叶子节点与叶子节点冗余；

总结

以上为个人经验，希望能给大家一个参考，也希望大家多多支持。