二叉树存储磁盘为什么要一页存一层节点的数据呢

[hackingwu]

二叉平衡树——>B Tree 是为了解决查询多层数据要多次 IO 的问题。 因为二叉树在存储到磁盘后，是一层存在一页。为了减少 IO ，所以要减少树的高度。 那我有一个问题？为什么要一页存一层节点的数据，不能一页存多层呢？ 是为了预留空间修改节点数据内容吗？

[Jooooooooo]

哪里看的...

二叉树只是一种结构而已, 和存储是无关的.

[hackingwu]

@Jooooooooo 那存到磁盘怎么存呢？

[liuxu]

加入于 2013-11-12 ，既然是上了年纪的老大哥，这个问题就要慎重对待了

这里的页我就作为磁盘的 block 说了

如果需要把内存中 B tree 数据结构存储到磁盘中，1 个页存储 1 层，或多页存储 1 层是最合理的
如果存储多层，假如 2 层和 3 层存储在一个页中，此时如果 2 层还增加 1 个节点，就必须把 3 层移到别的页中，然后在 2 层的页中插入，这就是 mysql/innodb 中常说的“页分裂”问题

[stein42]

如果用磁盘页来存储二叉树节点：
1 页存 1 层，最多 1 个 key-value ，2 个孩子，非常浪费空间。
1 页存 2 层，最多 3 个 key-value ，4 个孩子。
1 页存 3 层，最多 7 个 key-value ，8 个孩子。
...
1 页存 n 层，最多 2^n-1 个 key-value ，2^n 个孩子。
选择适当的 n ，使得空间刚好利用完。

这样的结构，再改进一下插入、删除操作，就得到了 B 树。

[hhjswf]

你怎么不问，为啥不把所有节点都存在一个内存块

[saberlong]

综合实现复杂度，节点检索性能等等的考虑吧。
1.一页一个节点。页的地址即可表示节点，那么可以直接根据页号找到对应节点数据。如果一页多节点还得额外存信息来索引节点所在位置，并且存取和更新都会有额外的复杂度，提高开发难度，对性能不友好。
2.一个节点可能跨页。当 key 或 value 数据过大时，需要跨页。至于跨页的分配管理得看实现。我以前写的是和节点页采用同一套页管理，加个特殊标识。而像 etcd 的底层 bbolt 是采用相邻连续页组合成一个页，这样开发复杂度降低，感觉空间浪费会多些。

[xilou31]

页的概念，本身就是一个有序的双向链表。

如果一页存多层，就不能用二分法进行节点的查找了，效率反而降低。

[xilou31]

#7 好像也不太对，双向链表不能用二分法