On Feb 3, 2011, at 3:38 AM, Simon Slavin <slav...@bigfraud.org> wrote:
> SQLite creates some indexes the programmer doesn't specifically ask for: on > the rowid, on the primary key, and on any column declared as UNIQUE. Of > course, in a particular table all three of these might actually be the same > column, so it might need just one. But every table has at least one index. The ROWID of a table doesn't have an "index," so it isn't really fair to say that every table has at least one index. At least, not when using the word "index" to mean a secondary data structure in the database that must be updated and maintained in conjunction with the table data structure. Both tables and indexes are stored within the SQLite file as a tree structure. The raw table data is stored in a tree structure that happens to be sorted by ROWID. For every index, SQLite creates an addition tree structure that is sorted by whatever columns make up the index. The structures are extremely similar, since they serve the same purpose. Both explicit indexes (CREATE INDEX...), and implicit indexes (non-integer PRIMARY KEYs, UNIQUE constraints) create additional tree structures in the database. However, if no PK is defined, or if the PK is defined as an INTEGER PRIMARY KEY, then no external index is created. The only data structure is the table itself. This is also why INTEGER PRIMARY KEYs are so desirable over other PK types. Not only do they reduce database size, by using the inherent structure of the main table data store as their "index," they also tend to be about twice as fast at doing explicit row lookups (vs a traditional index), as only one tree structure needs to be searched to retrieve any column. That speed difference means the break-even point for indexed lookup vs table scan for a set of INTEGER PK values is closer to 15% to 20% of the rows, vs the traditional 5% to 10% rule of thumb that applies to standard indexes. -j > Simon. > _______________________________________________ > sqlite-users mailing list > sqlite-users@sqlite.org > http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users _______________________________________________ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
