Lines Matching full:search

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.
60  * AUXILIARY SEARCH TREES:
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.
182  * the auxiliar search tree - when we're done searching the bset_float tree we
183  * have this many bytes left that we do a linear search over.
187  * cacheline in the linear search - but the linear search might stop before it
386 /* These assume r (the search key) is not a deleted key: */