lkml.org 
[lkml]   [2001]   [Dec]   [7]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
SubjectRe: [reiserfs-dev] Re: Ext2 directory index: ALS paper and benchmarks
Date
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
-
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/

\
 
 \ /
  Last update: 2005-03-22 13:13    [W:0.075 / U:0.308 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site