Kenneth McDonald wrote:
This cannot be done efficiently (at least not elegantly) with
explicit indexes. For example, let's say I'm using integer
indexes to define the order, and I have a table with one
million records. If I insert a new record halfway through
the table, then I have to update the integer column for
500,000 elements--hardly O(log(n)) performance :-)
It sounds like what you want is an efficient way to
compute the number of rows that come before (or after)
a particular row X.
Providing such a mechanism is not hard to do using the
same BTree algorithm of SQLite. I considered adding
that capability when I was designing the BTree logic
for both SQLite 2 and again for SQLite 3. Having the
ability to find the number of rows less than row X
allows operations such as count(*) to run much faster
(O(logN) instead of O(N)). But the down side is that
inserts and deletes require that O(logN) pages of the
database be modified instead of O(1) pages as is required
now. I decided that the performance of insert and delete
was more important than the performance of count(*) and
so I left that feature out.
--
D. Richard Hipp -- [EMAIL PROTECTED] -- 704.948.4565
