On Thu, Jun 30, 2011 at 12:29 PM, Jens Alfke <j...@mooseyard.com> wrote: > > On Jun 29, 2011, at 7:00 PM, sleepnova wrote: > >> I think what many people really concerned is the growing pattern of size as >> number of docs increase. (space complexity) >> (If it grows exponentially then that's not a good sign.) > > It’s basically linear, assuming the database gets compacted periodically. The > file format is a B-tree, like most other databases, so the extra space for > interior nodes is going to be O(log n). Views, like traditional indexes, also > occupy B-tree nodes, so depending on how many of those you have, they’ll > occupy some extra space, but also probably a lot less than the documents > themselves. > > It sounds like append-only writing and compaction are confusing to some > people. They’re not really very complicated. If you have some familiarity > with garbage collection, CouchDB works almost exactly like a copying > collector[1]: new objects are allocated simply by bumping a pointer, and > collection works by copying the live objects into a new space, then > discarding the old one. By contrast, most other databases work like a regular > memory allocator: freeing obsolete objects in place, keeping a map of free > space, and reallocating that space to new objects later. > > —Jens > > [1] > http://en.wikipedia.org/wiki/Garbage_collection_(computer_science)#Copying_vs._mark-and-sweep_vs._mark-and-don.27t-sweep
Just a heads up that I'm going to be stealing that description. :D
