On 1/6/18, Dinu <dinumar...@gmail.com> wrote: > > I think b-trees can store the counts of descendant nodes for every node to > solve this issue in O(log n), but I don't see anything like it in the SQLite > format.
They can do that, but it also means that all the parent b-tree pages must be updated whenever an entry is added or removed from a leaf page, which increases the amount of I/O needed for operations like INSERT, DELETE, or UPDATE. It seemed to me that INSERT, DELETE, and UPDATE are rather more common than SELECT count(*), so I decided not to keep a child count in the b-tree pages when I first designed the current b-tree format for SQLite..... back in 2003. -- D. Richard Hipp d...@sqlite.org _______________________________________________ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
