[PATCH 06/14] repair: use a btree instead of a radix tree for theprefetch queue

[Dave Chinner]

On Thu, Nov 12, 2009 at 05:04:08AM -0500, Christoph Hellwig wrote:
> On Wed, Oct 21, 2009 at 12:12:33PM -0500, Alex Elder wrote:
> > - Related to the previous one--it would be good to have
> >   a little info about why the value 7 was chosen as the
> >   number of keys per node.  Perhaps I just don't know
> >   enough of the history (or content of the upcoming
> >   patches).

I think I can answer this one:

> +/*
> + * Maximum number of keys per node.  Must be greater than 2 for the code
> + * to work.
> + */
> +#define BTREE_KEY_MAX		7
> +#define BTREE_KEY_MIN		(BTREE_KEY_MAX / 2)
> +
> +#define BTREE_PTR_MAX		(BTREE_KEY_MAX + 1)
> +
> +struct btree_node {
> +	unsigned long		num_keys;
> +	unsigned long		keys[BTREE_KEY_MAX];
> +	struct btree_node	*ptrs[BTREE_PTR_MAX];
> +};

BTREE_KEY_MAX = 7 results in a btree_node exactly filling
a 64 byte cacheline on 32 bit, and 2 cachelines on 64 bit.
Cacheline aligned and sized nodes minimises the number of cache
misses when traversing/searching the btree....

Cheers,

Dave.
-- 
Dave Chinner
david at fromorbit.com