"Scott Hess" <[EMAIL PROTECTED]> wrote: > On 6/20/07, Andrew Finkenstadt <[EMAIL PROTECTED]> wrote: > > How difficult do you think it would be to support an alternative method of > > indexing within SQLite specifically to support O(1) retrieval of the rowid > > for a table, and then potentially O(1) retrieval of the row data for a > > table, when in-order retrieval is undesired?
It's a major rewrite. SQLite assumes btree access in a number of important places. > > > > My database design is highly specialized to never, ever retrieve data except > > by whole-key equality, and would benefit greatly from this optimization. > > I'm willing to code it up myself, although I'm not quite set up to do SQL > > syntax parser changes, preferring to use the amalgamation. > > Would you be able to live with converting your primary key to a 64-bit > hash value? In development of fts2, I found that direct rowid -> row > access is pretty fast. It's still technically O(logN), but the log's > base is absurdly large, so it comes reasonably close to O(1). I concur with Scott's assessment. The typical fanout in the table btrees used by SQLite is around 100 (assuming a 1K page) so you can get to one of 10 million pages in only 3 page reads. And the first page is almost guaranteed to be in cache, so really only 2 page reads. -- D. Richard Hipp <[EMAIL PROTECTED]> ----------------------------------------------------------------------------- To unsubscribe, send email to [EMAIL PROTECTED] -----------------------------------------------------------------------------
