Messages in this thread | | | From | Daniel Phillips <> | Subject | Re: [reiserfs-dev] Re: Ext2 directory index: ALS paper and benchmarks | Date | Fri, 7 Dec 2001 15:35:55 +0100 |
| |
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/
| |