|
Linux Kernel
3.7.1
|
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
|
Linux Kernel
3.7.1
|
#include <btree.h>
Data Fields | |
| unsigned long * | node |
| mempool_t * | mempool |
| int | height |
DOC: B+Tree basics
A B+Tree is a data structure for looking up arbitrary (currently allowing unsigned long, u32, u64 and 2 * u64) keys into pointers. The data structure is described at http://en.wikipedia.org/wiki/B-tree, we currently do not use binary search to find the key on lookups.
Each B+Tree consists of a head, that contains bookkeeping information and a variable number (starting with zero) nodes. Each node contains the keys and pointers to sub-nodes, or, for leaf nodes, the keys and values for the tree entries.
Each node in this implementation has the following layout: [key1, key2, ..., keyN] [val1, val2, ..., valN]
Each key here is an array of unsigned longs, geo->no_longs in total. The number of keys and values (N) is geo->no_pairs. struct btree_head - btree head
: the first node in the tree : mempool used for node allocations : current of the tree
1.8.2