3 ms·
http://www.stanford.edu/class/cs276a/projects/docs/berkeleydb/ref/am_conf/cachesize.html http://www.stanford.edu/class/cs276a/projects/docs/berkeleyd... describ
by btilly 14y ago
http://www.stanford.edu/class/cs276a/projects/docs/berkeleydb/ref/am_conf/cachesize.html http://www.stanford.edu/class/cs276a/projects/docs/berkeleyd... describes the performance of BTree data structures in real world databases. (It is discussing a standalone key/value store, but the internals of a database index work the same way.)
As noted, 3 levels suffices for a moderate sized table, and it would be rare to need more than 5 levels. The "levels" in question are pages of memory that have to be looked at. The reason that this is less than you expect is that inside of each page you essentially have a tree that has several levels to traverse. However the time to traverse that tree is less than the time to fetch the next page, so the operations of concern are fetches of pages.
The most important number noted in that link is that under normal operation once caches are warmed up, it should a maximum of one disk seek to traverse the index. That single disk seek, if it happens, takes longer than all other operations.
The long and short of it is, "in theory log(n), in practice a reasonably small constant."
- Someone 14y agoThanks. But a disk seek is not a small constant. I would almost describe that as "in theory log(n), in practice a disk seek, so half the speed" (assuming that the record can be written with one disk seek)
- jeltz 14y agoA hash index will also require one disk seek which makes b-tree indexes and hash indexes have more similar performance than the theoretical O(log n) vs O(1) would indicate.