>On December 7, 2001 01:13 am, Hans Reiser wrote:
>
>>Daniel Phillips wrote:
>>
>>>Fully understanding your code is going to take some time. This would
>>>go faster if I could find the papers mentioned in the comments, can you point
>>>me at those?
>>>
>>Which papers in which comments?
>>
>
> http://innominate.org/~graichen/projects/lxr/source/include/linux/reiserfs_fs.h?v=v2.4#L1393
>
> 1393 create a new node. We implement S1 balancing for the leaf nodes
> 1394 and S0 balancing for the internal nodes (S1 and S0 are defined in
> 1395 our papers.)*/
>
>--
>Daniel
>
>
How about I just explain it instead? We preserve a criterion of nodes
must be 50% full for internal nodes and criterion of no 3 nodes can be
squeezed into 2 nodes for leaf nodes.
A tree that satisfies the criterion that no N nodes can be squeezed into
N-1 nodes is an SN tree. I don't remember where Konstantin Shvachko
published his paper on this, maybe it can be found.
In Reiser4 we abandon the notion that fixed balancing criteria should be
used for leaf nodes.
Hans
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/