b+树的最大和最小高度可以是同一个值吗？
Can the max and min height of b+ tree be the same value?
我有这个信息：
- 1000 万条记录。
- 每条记录为 256 字节。
- 每条记录都有一个 32 字节的索引字段。
- 我们系统的磁盘块大小是8KB。
- 我们的系统是 32 位的，所以指针是 4 个字节。 （将此用于 links！）。
我想求出这棵B+树的最大和最小高度。当我确实有相同的最大值和最小值时，这可能吗？如果不是你能指出错误吗？
我走过的路
DATA NODE相关计算
假设L为Data Node（叶节点）中的数据个数
- 节点大小=数据计数*记录大小
- 8KB = L * 256 字节
- 8192 字节 = L * 256 字节
- L = 8192 / 256
- 长=32
记住：数据节点最多可以存储32条记录！所以，每个数据节点的最大数据数是32。这意味着，一个数据节点至少可以存储32/2=16个数据在least/minimum!
所以
- 最小数据计数为 16
- 最大数据数为 32
索引节点相关计算
- 节点大小 = (M – 1) * index/key + M * links（指针）
- 8KB = (M – 1) * 32 字节 + M * 4 字节
- 8192 字节 = (M – 1) * 32 + 4* M
- 8192 = 36M – 32
- 36M = 8224
- 男=228
我们的数据节点最多可以存储 32 条记录，最少 16 条记录。我们的索引节点最多可以存储 227 个索引，最少 113 个索引。
寻找最小值：
- 1000 万条记录 = 32 条记录 * leaf/data 节点数
- 叶子节点数=1000万/32
- 叶节点数 = 312500
所以，要存储 1000 万条记录，我们需要 312500 个完整的数据节点！
对于 312500 个数据节点，我们需要来自索引节点的 312500 links！
- 312500 = link 计数 * 索引节点
- 312500 = 228 * 索引节点
- 索引节点 = 1370
- 因为1370比228大。这意味着我们需要有上索引节点！
- 1370 = 228 * 上索引节点
- upper index nodes = 6 小于228。这意味着我们需要在这6个索引节点之上有一个根节点！
所以最小高度是 3:
寻找最大值：
- 1000 万条记录 = 16 条记录 * leaf/data 节点数
- 叶子节点数=1000万/16
- 叶节点数 = 625000
所以，要存储 1000 万条记录，我们需要 625000 个完整的数据节点！
对于 625000 个数据节点，我们需要来自索引节点的 625000 links！
- 625000 = link 计数 * 索引节点数
- 625000 = 228 * 索引节点
- 索引节点 = 2741
因为2741比228大。这意味着我们需要有上索引节点！
- 2741 = 228 * 上索引节点
upper index nodes = 12 小于228。这意味着我们需要在这12个索引节点之上有一个根节点！
问题：所以最大高度也是3？
是的，这完全有可能。根将获得的 children 数量明显不同，在第一种情况下很小，在第二种情况下是它的倍数。
我应该注意到你有一些错误。主要错误是在最后一部分（“寻找最大值”）中，您没有将索引节点的使用减少到其容量的一半。您继续使用 228，而您本应使用 114。
其次，在第一种情况下，您需要向上舍入分区，因为您将需要一个额外的节点来覆盖剩余的分区（从相邻节点重新分配一些键）。在第二种情况下向下舍入是正确的，这意味着你需要将除法的剩余部分添加到一个节点（因为它有空间）。
这些更正不会影响两种情况下都需要 3 个级别的最终结论。概述：
Fill style
Records / leaf
Keys / index
Data nodes
Level 3
Level 2
Level 1
compact
32
228
312500
1371
7
1
sparse
16
114
625000
5482
49
1
我有这个信息：
- 1000 万条记录。
- 每条记录为 256 字节。
- 每条记录都有一个 32 字节的索引字段。
- 我们系统的磁盘块大小是8KB。
- 我们的系统是 32 位的，所以指针是 4 个字节。 （将此用于 links！）。
我想求出这棵B+树的最大和最小高度。当我确实有相同的最大值和最小值时，这可能吗？如果不是你能指出错误吗？
我走过的路
DATA NODE相关计算
假设L为Data Node（叶节点）中的数据个数
- 节点大小=数据计数*记录大小
- 8KB = L * 256 字节
- 8192 字节 = L * 256 字节
- L = 8192 / 256
- 长=32
记住：数据节点最多可以存储32条记录！所以，每个数据节点的最大数据数是32。这意味着，一个数据节点至少可以存储32/2=16个数据在least/minimum!
所以
- 最小数据计数为 16
- 最大数据数为 32
索引节点相关计算
- 节点大小 = (M – 1) * index/key + M * links（指针）
- 8KB = (M – 1) * 32 字节 + M * 4 字节
- 8192 字节 = (M – 1) * 32 + 4* M
- 8192 = 36M – 32
- 36M = 8224
- 男=228
我们的数据节点最多可以存储 32 条记录，最少 16 条记录。我们的索引节点最多可以存储 227 个索引，最少 113 个索引。
寻找最小值：
- 1000 万条记录 = 32 条记录 * leaf/data 节点数
- 叶子节点数=1000万/32
- 叶节点数 = 312500
所以，要存储 1000 万条记录，我们需要 312500 个完整的数据节点！
对于 312500 个数据节点，我们需要来自索引节点的 312500 links！
- 312500 = link 计数 * 索引节点
- 312500 = 228 * 索引节点
- 索引节点 = 1370
- 因为1370比228大。这意味着我们需要有上索引节点！
- 1370 = 228 * 上索引节点
- upper index nodes = 6 小于228。这意味着我们需要在这6个索引节点之上有一个根节点！
所以最小高度是 3:
寻找最大值：
- 1000 万条记录 = 16 条记录 * leaf/data 节点数
- 叶子节点数=1000万/16
- 叶节点数 = 625000
所以，要存储 1000 万条记录，我们需要 625000 个完整的数据节点！
对于 625000 个数据节点，我们需要来自索引节点的 625000 links！
- 625000 = link 计数 * 索引节点数
- 625000 = 228 * 索引节点
- 索引节点 = 2741
因为2741比228大。这意味着我们需要有上索引节点！
- 2741 = 228 * 上索引节点
upper index nodes = 12 小于228。这意味着我们需要在这12个索引节点之上有一个根节点！
问题：所以最大高度也是3？
是的，这完全有可能。根将获得的 children 数量明显不同，在第一种情况下很小，在第二种情况下是它的倍数。
我应该注意到你有一些错误。主要错误是在最后一部分（“寻找最大值”）中，您没有将索引节点的使用减少到其容量的一半。您继续使用 228，而您本应使用 114。
其次，在第一种情况下，您需要向上舍入分区，因为您将需要一个额外的节点来覆盖剩余的分区（从相邻节点重新分配一些键）。在第二种情况下向下舍入是正确的，这意味着你需要将除法的剩余部分添加到一个节点（因为它有空间）。
这些更正不会影响两种情况下都需要 3 个级别的最终结论。概述：
| Fill style | Records / leaf | Keys / index | Data nodes | Level 3 | Level 2 | Level 1 |
|---|---|---|---|---|---|---|
| compact | 32 | 228 | 312500 | 1371 | 7 | 1 |
| sparse | 16 | 114 | 625000 | 5482 | 49 | 1 |