"Mrs. Brisby" <[EMAIL PROTECTED]>
07/11/2003 12:50 PM
To: [EMAIL PROTECTED]
cc: [EMAIL PROTECTED]
Subject: Re: [sqlite] Performance problem
> On Thu, 2003-11-06 at 19:00, [EMAIL PROTECTED] wrote:
> > How would you handle the lack of ordering associate with hash tables?
> > Sqlite can currently use indicies for three main tests: equals, less
than,
> > and greater than. While hash-tables are good at finding equal-to in
> > constant time it usually means linear time (a table-scan) to test for
less
> > than or greater than. Do you have a solution to this problem?
> You presume that a defining characteristic of a hash-table is that the
> function be non-linear. Consider a n->3 bit function:
> f(x) -> x mod 8
> A very linear function that it is perfectly easy to iterate _in_order_
> all values of the table.
I must be having a "stupid" day.
To simplify your function I'll draw up a table assuming mod 4 instead of 8
and input the numbers 0-11:
mod value Values collected in this bucket
0 0, 4, 8
1 1, 5, 9
2 2, 6, 10
3 3, 7, 11
As I understand it you would leave the bucket as a B-tree and have the
hash at the root. To exercise the clause WHERE value < 4 you would still
need to look in each bucket, resulting in 4 smaller B-tree lookups and
iterates compared to the current single lookup and iterate... and would
also require the the results of each iteration be combined and sorted.
Maybe you'd do it the other way instead, and have a B-tree at the root
(I'll simplify this as a binary tree for the example... sorry about the
ascii art):
0-Hash of 0,1,2,3
/
/
4-Hash of 4,5,6,7
\
\
8-Hash of 8,9,10,11
I guess in this case the hashes aren't really hashes anymore, they're more
like arrays. There wouldn't be any bucket under hash unless the key was
identical for two values. The B-tree entry becomes x div 4 (or an
appropriate number). This might allow quicker equality tests without
compromising less than and greater than tests. Is this the kind of
structure you're endorsing?
Benjamin.
---------------------------------------------------------------------
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
