Re: [PATCH] add b+tree library

Pavel Machek
2009-01-17T23:13:47Z

Hi!

> --- /dev/null 1970-01-01 00:00:00.000000000 +0000
> +++ wireless-testing/lib/btree.c 2009-01-10 11:41:47.000000000 +0100
> @@ -0,0 +1,797 @@
> +/*
> + * lib/btree.c - Simple In-memory B+Tree
> + *
> + * As should be obvious for Linux kernel code, license is GPLv2
> + *
> + * Copyright (c) 2007-2008 Joern Engel <joern@logfs.org>
> + * Bits and pieces stolen from Peter Zijlstra's code, which is
> + * Copyright 2007, Red Hat Inc. Peter Zijlstra <pzijlstr@redhat.com>
> + * GPLv2
> + *
> + * see http://programming.kicks-ass.net/kernel-patches/vma_lookup/btree.patch
> + *
> + * A relatively simple B+Tree implementation. I have written it as a learning
> + * excercise to understand how B+Trees work. Turned out to be useful as well.
> + *
> + * B+Trees can be used similar to Linux radix trees (which don't have anything
> + * in common with textbook radix trees, beware). Prerequisite for them working
> + * well is that access to a random tree node is much faster than a large number
> + * of operations within each node.

should be 'much slower'?

Because otherwise I don't get it.

--
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html