4 ms·

Memcached allows for O(1) lookups. Your database server probably uses b-tree indexes which are great, but they're log(n) lookups. A B-tree lookup also requires

by palish 18y ago

Memcached allows for O(1) lookups. Your database server probably uses b-tree indexes which are great, but they're log(n) lookups. A B-tree lookup also requires reading from the harddrive, which can require a lot more time than reading from memory.

mdasen 18y ago
Why? There's no reason that a b-tree must be stored on a hard drive. In fact, there's no reason why MySQL can't exist entirely in memory for read purposes (clearly you want writes written to the disk). I'm not going to comment on configuring specific databases, but there's nothing about b-tree data structures that means you couldn't create an entirely in-memory data store that used b-tree indexes. The difference between disk and memory storage is MemcacheDB and memcached. RDBMS love to leave stuff in memory if they can and that makes the reads skip the harddrive.
- palish 18y ago
  You are technically correct. My words were imprecise -- indexing into a B-tree does not require accessing the harddrive. But it is a rather large possibility, and it's something to be aware of. From Wikipedia ( http://en.wikipedia.org/wiki/B-tree http://en.wikipedia.org/wiki/B-tree ): "B-trees have substantial advantages over alternative implementations when node access times far exceed access times within nodes. This usually occurs when most nodes are in secondary storage such as hard drives. By maximizing the number of child nodes within each internal node, the height of the tree decreases, balancing occurs less often, and efficiency increases. Usually this value is set such that each node takes up a full disk block or an analogous size in secondary storage. While 2-3 B-trees might be useful in main memory, and are certainly easier to explain, if the node sizes are tuned to the size of a disk block, the result might be a 257-513 B-tree (where the sizes are related to larger powers of 2)." So yes, "there's no reason that a b-tree must be stored on a hard drive". There's also no reason why a car couldn't also have a built-in toaster. :) As far as in-memory data structures go, there are better choices than B-trees. Why use a suboptimal data structure?

by palish 18y ago

mdasen 18y ago

Why? There's no reason that a b-tree must be stored on a hard drive. In fact, there's no reason why MySQL can't exist entirely in memory for read purposes (clearly you want writes written to the disk). I'm not going to comment on configuring specific databases, but there's nothing about b-tree data structures that means you couldn't create an entirely in-memory data store that used b-tree indexes. The difference between disk and memory storage is MemcacheDB and memcached. RDBMS love to leave stuff in memory if they can and that makes the reads skip the harddrive.

palish 18y ago
You are technically correct. My words were imprecise -- indexing into a B-tree does not require accessing the harddrive. But it is a rather large possibility, and it's something to be aware of. From Wikipedia ( http://en.wikipedia.org/wiki/B-tree http://en.wikipedia.org/wiki/B-tree ): "B-trees have substantial advantages over alternative implementations when node access times far exceed access times within nodes. This usually occurs when most nodes are in secondary storage such as hard drives. By maximizing the number of child nodes within each internal node, the height of the tree decreases, balancing occurs less often, and efficiency increases. Usually this value is set such that each node takes up a full disk block or an analogous size in secondary storage. While 2-3 B-trees might be useful in main memory, and are certainly easier to explain, if the node sizes are tuned to the size of a disk block, the result might be a 257-513 B-tree (where the sizes are related to larger powers of 2)." So yes, "there's no reason that a b-tree must be stored on a hard drive". There's also no reason why a car couldn't also have a built-in toaster. :) As far as in-memory data structures go, there are better choices than B-trees. Why use a suboptimal data structure?