这是一个创建于 754 天前的主题，其中的信息可能已经有所发展或是发生改变。
二叉平衡树——>B Tree 是为了解决查询多层数据要多次 IO 的问题。 因为二叉树在存储到磁盘后，是一层存在一页。为了减少 IO ，所以要减少树的高度。 那我有一个问题？为什么要一页存一层节点的数据，不能一页存多层呢？ 是为了预留空间修改节点数据内容吗？
 |
1
Jooooooooo 2022-10-30 13:24:54 +08:00
哪里看的...
二叉树只是一种结构而已, 和存储是无关的. |
 |
2
hackingwu OP @Jooooooooo 那存到磁盘怎么存呢？
|
 |
3
liuxu 2022-10-30 15:51:11 +08:00
加入于 2013-11-12 ，既然是上了年纪的老大哥，这个问题就要慎重对待了
这里的页我就作为磁盘的 block 说了 如果需要把内存中 B tree 数据结构存储到磁盘中，1 个页存储 1 层，或多页存储 1 层是最合理的 如果存储多层，假如 2 层和 3 层存储在一个页中，此时如果 2 层还增加 1 个节点，就必须把 3 层移到别的页中，然后在 2 层的页中插入，这就是 mysql/innodb 中常说的“页分裂”问题 |
 |
4
stein42 2022-10-30 16:26:20 +08:00
如果用磁盘页来存储二叉树节点：
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 树。 |
 |
5
hhjswf 2022-10-30 17:57:20 +08:00 via Android
你怎么不问，为啥不把所有节点都存在一个内存块
|
 |
6
saberlong 2022-10-30 20:32:05 +08:00 via Android
综合实现复杂度，节点检索性能等等的考虑吧。
1.一页一个节点。页的地址即可表示节点，那么可以直接根据页号找到对应节点数据。如果一页多节点还得额外存信息来索引节点所在位置，并且存取和更新都会有额外的复杂度，提高开发难度，对性能不友好。 2.一个节点可能跨页。当 key 或 value 数据过大时，需要跨页。至于跨页的分配管理得看实现。我以前写的是和节点页采用同一套页管理，加个特殊标识。而像 etcd 的底层 bbolt 是采用相邻连续页组合成一个页，这样开发复杂度降低，感觉空间浪费会多些。 |
 |
7
xilou31 2022-10-30 21:14:52 +08:00
页的概念，本身就是一个有序的双向链表。
如果一页存多层，就不能用二分法进行节点的查找了，效率反而降低。 |
|
8
xilou31 2022-10-30 21:16:59 +08:00
#7 好像也不太对，双向链表不能用二分法
|
Select Language