在MongoDB中使用索引的运行时间 [英] runtime of using indexing in mongodb

问题描述

根据MongoDB的文档

Based on mongodb documentation

在 ensureIndex（）函数仅创建，如果它不存在索引。

The ensureIndex() function only creates the index if it does not exist.

在一个集合索引的一个关键，在查询前pressions随机访问相匹配的 指定的键是快速。如果没有索引，MongoDB的要经过的每个文档中的查询检查指定键的值：

Once a collection is indexed on a key, random access on query expressions which match the specified key are fast. Without the index, MongoDB has to go through each document checking the value of specified key in the query:

db.things.find({j:2});  // fast - uses index
db.things.find({x:3});  // slow - has to check all because 'x' isn't 

这是否意味着code运行时的一号线是 big_theta = 1 ，和code第2行是 big_theta = ñ？

Does that mean the 1st line of code runtime is big_theta = 1, and 2nd line of code is big_theta = n ?

推荐答案

MongoDB使用B树索引，因为可以在源$ C ​​$下的 index.cpp中。这意味着，查找可pssed为 EX $ P $ O（日志N），其中N为文件的数量，但它也是 O（ D）如果D是树的深度（假设树有点平衡）。 D是通常非常小，因为每个节点都会有许多孩子。

MongoDB uses B-tree for indexing, as can be seen in the source code for index.cpp. This means that lookups can be expressed as O(log N) where N is the number of documents, but it is also O(D) if D is the depth of the tree (assuming the tree is somewhat balanced). D is usually very small because each node will have many children.

儿童在MongoDB中节点数量约为8192（的 btree.h ）这样的指标有几个十亿文件可能适合在树上，只有3个级别！您可以轻松地认识到，对数不log_2（如二进制树），而是log_8192，生长极为缓慢。

The number of children in a node in MongoDB is about 8192 (btree.h) so an index with a few billion documents may fit in a tree with only 3 levels! You easily realize that the logarithm is not log_2 (as in binary trees) but instead log_8192, which grows extremely slowly.

正因为如此，B树通常被视为常数时间查找， O（1），在实践中。

Because of this, b-trees are usually regarded as constant-time lookup, O(1), in practice.

另一个很好的理由让许多儿童在每一个节点是索引存储在磁盘上。你想尝试使用一个磁盘块中的所有空间，一个节点来提高缓存的性能并减少磁盘寻道。 B树都有很好的磁盘性能，因为你只需要访问很少的节点找到你所期待的。

Another good reason for keeping many children in each node is that the index is stored on disk. You want to try to utilize all the space in a disk block for one node to improve cache performance and reduce disk seeks. B-trees have very good disk performance because you only need to visit very few nodes to find what you are looking for.

这篇关于在MongoDB中使用索引的运行时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！