Re: [reiserfs-dev] Re: Ext2 directory index: ALS paper and benchmarks

[Hans Reiser]

Daniel Phillips wrote:

>On December 7, 2001 01:36 pm, Hans Reiser wrote:
>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.)*/
>>>
>>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.
>>
>
><nit> Then shouldn't that be "S3 balancing for the leaf nodes and S2 
>balancing for the internal nodes"?
>
>--
>Daniel
>
>
Yes, sorry, an SN tree has the property that at the end of balancing the 
set of nodes within the sweep composed of nodes N to the left and N to 
the right plus the node being balanced cannot be compressed into 2N nodes.

My error.

Hans