On Tue, Jun 22, 2010 at 3:08 PM, Eric Smith <eas....@gmail.com> wrote:
> I have confirmed that INSERT times are roughly logarithmic in > the number of existing records after creating my specific user > indices. > > But INSERT times appeared to be *linear* in the number of existing > records before I had created any user indices (and with no primary > keys or unique indices defined). > > Can anyone explain this? > When there are no indices, SQLite can put the rows into the database in any order it wants, and it chooses to put them in ascending order. Thus, each insert becomes a constant-time append. (Approximately - the truth is a little more complicated, but by waving our arms vigorously, we can still claim constant time per row.) But if there are indices, each row must be inserted in index order, which involves a b-tree search to find the right spot and possible a rebalancing operation - O(logN) per row. > > Eric > > > time (minutes) to insert 2m records > > 10 > ++----------+----------+-----------+----------+-----------+---------++ > > + + + + A + + > + > > 9 > ++..................................................AAAA............++ > > | AAA AAAAA > | > > 8 > ++..........................................AAA..AAAAA..............++ > > | A AAAA > | > > 7 > ++.....................A.............A..AAAAAAA.....................++ > > | AAAA > | > > 6 > ++..................AA...........A.AAAAA............................++ > > | AAAAAAA > | > > 5 > ++....................A...AAAAAA....................................++ > > 4 > ++.........AA.AA..AAAAA.AAAAA.......................................++ > > | A AAAAAAA AA > | > > 3 > ++............AAAA..................................................++ > > | AAA A A > | > > 2 > ++.........AA...........................................AAAAAAAA....++ > > | AA > | > > 1 > ++...AAAAAAA........................................................++ > > AAAAAAA + + + + + > + > > 0 > ++----------+----------+-----------+----------+-----------+---------++ > > 0 100 200 300 400 500 > 600 > > millions of existing records > > -- > Eric A. Smith > > A nickel ain't worth a dime anymore. > -- Yogi Berra > _______________________________________________ > sqlite-users mailing list > sqlite-users@sqlite.org > http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users > -- --------------------- D. Richard Hipp d...@sqlite.org _______________________________________________ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
