Database Reference
In-Depth Information
["Edwards", 21]
["Perry", 18]
(Preallocated space)
Bucket
["Adams", 17]
["Banks", 27]
(Preallocated space)
["Richards", 19]
["Ryan", 20]
(Empty)
Bucket
Bucket
["Grant", 19]
["Morton", 27]
(Preallocated space)
Bucket
Figure 7.5
Sample B-tree structure
A B-tree, as you might guess, is a tree-like data structure. Each node in the tree can
contain multiple keys. You can see in the example that the root node contains two
keys, each of which is in the form of a
BSON
object representing an indexed value
from the
users
collection. So in reading the contents of the root node, you can see
the keys for two documents, indicating last names Edwards and Perry, with ages of 21
and 18, respectively. Each of these keys includes two pointers: one to the data file it
belongs to and another to the child node. Additionally, the node itself points to
another node with values less than the node's smallest value.
One thing to notice is that each node has some empty space (not to scale). In
MongoDB's B-tree implementation, a new node is allocated 8,192 bytes, which means
that in practice, each node may contain hundreds of keys. This depends on the aver-
age index key size; in this case, that average key size might be around 30 bytes. The
maximum key size in MongoDB v2.0 is 1024 bytes. Add to this a per-key overhead of
18 bytes and a per-node overhead of 40 bytes, and this results in about 170 keys per
node.
7
This is relevant because users frequently want to know why index sizes are what
they are. So you now know that each node is
8 KB
, and you can estimate how many
keys will fit into each node. To calculate this, keep in mind that B-tree nodes are usu-
ally intentionally kept around 60% full by default.
If the preceding made sense, then in addition to gaining a superficial mental
model of B-trees, you should walk away with some ideas about how they use space and
how they're maintained: a couple more reminders that indexes aren't free. Choose
them carefully.
7.2
Indexing in practice
With most of the theory behind us, we'll now look at some refinements on our con-
cept of indexing in MongoDB. We'll then proceed to some of the niceties of index
administration.
7
(8192 - 40) / (30 + 18) = 169.8
