md/bcache/bset.h

47  * We implement code here for creating and maintaining auxiliary search trees
54  * to search entire btree nodes and iterate over them in sorted order.
58  * point (if you pass it a search key) or the start of the btree node.
62  * Since keys are variable length, we can't use a binary search on a bset - we
73  * set; they index one key every BSET_CACHELINE bytes, and then a linear search
77  * into, we construct a binary search tree in an array - traversing a binary
78  * search tree in an array gives excellent locality of reference and is very
88  * Nodes in the auxiliary search tree must contain both a key to compare against
93  * search tree corresponds to precisely BSET_CACHELINE bytes in the set. We have
100  * search tree at every iteration we know that both our search key and the key
102  * comparisons. (We special case the start of a search so that this is true even
111  * key our auxiliary search tree node corresponds to, and key p, the key
113  * search tree is the highest bit that differs between n and p.
116  * comparison. But we'd really like our nodes in the auxiliary search tree to be
127  * The keys in the auxiliary search tree are stored in (software) floating
135  * search trees take up 3% as much memory as the btree itself.
137  * Constructing these auxiliary search trees is moderately expensive, and we
138  * don't want to be constantly rebuilding the search tree for the last set
142  * within each byte range works the same as with the auxiliary search trees.
225 	 * Sets of sorted keys - the real btree node - plus a binary search tree
338 				 struct bkey *search);
341 			       const struct bkey *search);
344  * Returns the first key that is strictly greater than search
348 					   const struct bkey *search)
350 	return search ? __bch_bset_search(b, t, search) : t->data->start;