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

[Hans Reiser <reiser@namesys.com>]

Daniel Phillips wrote:

>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