二叉平衡树——>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 好像也不太对,双向链表不能用二分法
|