关于 B+树索引的问题

• 資深大佬 : nthhdy

  我的理解是，前者是对的，节点的大小是固定的。每条记录（或者索引）占用空间小，节点就可以放更多的记录。树的高度就倾向于比较小，查询会相对快。

• 資深大佬 : geebos

  节点的大小是可变的，节点越大，单个 page 可存储的节点就越少，反之则越多。

  参考： https://dev.mysql.com/doc/internals/en/innodb-fil-header.html

• 資深大佬 : auxox

  数据库系统中 B 树没有固定的阶。我认为不用固定阶的原因是很难计算一个 page 能存放多少记录，因为很多记录是变长的。因此对于大部分采用 B 树实现的存储系统来说，它们只是当 page 装不下新插入的记录时，就会分裂。当 page 比较’空旷’时就会 merge 。另外，并不是所有的基于 B 树的存储引擎都采用固定大小的 page 。

• 資深大佬 : geebos

  @geebos 放错了，应该是这个 https://dev.mysql.com/doc/internals/en/innodb-overview.html

• 資深大佬 : andj4cn

  应该 page 大小是固定的，page 除了保存头信息外，剩下的空间保存指向子 page 的 KV 指针。指针 pair 的大小是内置的，page 大小也是固定的。我的理解是，每个 page 能保存的最大子 page 指针对也是固定的。达到最大值则该 page 分裂，小于 B+ 树的要求则合并。

• 主 資深大佬 : zxCoder

  @andj4cn 索引的 key 大小应该是不固定的吧我觉得，比如一个 int 和一个 bigint，同一个 page 来存这些 key，应该数量会不一样

• 主 資深大佬 : zxCoder

  @auxox “数据库系统中 B 树没有固定的阶。我认为不用固定阶的原因是很难计算一个 page 能存放多少记录” 这句话我不太能理解，我的理解是，如果不是固定的阶，不就等同于每次都要计算一个 page 能存放多少记录吗？那为什么是很难计算呢？

• 資深大佬 : andj4cn

  @zxCoder 确实，指向子 page 的 KV 里的 k 应该是不固定的。pairs_num_max = (page_size – header_size)/(pair_size)，由于 pair_size 不固定而导致 page 可存储的 pairs 最大数量不固定。

• 資深大佬 : saberlong

  页大小可以选择，决定了就固定了。所以要么 key 有长度限制，要么引入其它结构处理超大 key 和 value 。记得 mysql 是有 key 长限制的。最新的版本不清楚

• 資深大佬 : saberlong

  我自己写的 b+树选择了不固定阶，key 有长度限制，value 不限。过大的 value 通过扩展页分割存储到多个页中。