D. Richard Hipp wrote: >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.
For web applications (sqlite being now the default database for PHP5), COUNT(*) performance is more important than INSERTs and DELETEs performance. The obvious reason is that a web page cannot display too many results, so you have to divide the result sets into pages. In order to prodide links to those pages, you need to constantly know how many pages there are. Big INSERTs in web applications are very rare. Bertrand Mansion Mamasam
