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

[Daniel Phillips]

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