algorithm - mongodb的数组操作的算法复杂度

Question

Mongodb 支持许多有用的数组操作，例如 $push 和 $pop，但我似乎找不到任何关于它们的算法复杂性的信息，也找不到它们是如何实现的以找出它们的运行时复杂性。任何帮助将不胜感激。

Answer 1

我认为当谈到 Mongo 更新时，只有三个相关案例：

1) 就地原子更新。例如，只需增加一个整数。这是非常快的。

2) 就地替换。必须重写整个文档，但它仍然适合当前空间（它缩小或有足够的填充）。

3) 文件迁移。您必须将文档写入新位置。

除此之外，还有更新受影响索引的成本（全部，如果必须移动整个事物）。

您在文档中实际执行的操作（推动数组、添加字段）不应该对操作的总成本产生任何重大影响，这似乎主要线性地取决于文档的大小（网络和磁盘传输成本） ）。

Answer 2

这是它们的实施位置。你可以从那里找出复杂性。

例如，这是$pop运算符（这对我来说似乎是 O(N)）：

    case POP: {
        uassert( 10135 ,  "$pop can only be applied to an array" , in.type() == Array );
        BSONObjBuilder bb( builder.subarrayStart( shortFieldName ) );

        int n = 0;

        BSONObjIterator i( in.embeddedObject() );
        if ( elt.isNumber() && elt.number() < 0 ) {
            // pop from front
            if ( i.more() ) {
                i.next();
                n++;
            }

            while( i.more() ) {
                bb.appendAs( i.next() , bb.numStr( n - 1 ) );
                n++;
            }
        }
        else {
            // pop from back
            while( i.more() ) {
                n++;
                BSONElement arrI = i.next();
                if ( i.more() ) {
                    bb.append( arrI );
                }
            }
        }

        ms.pushStartSize = n;
        verify( ms.pushStartSize == in.embeddedObject().nFields() );
        bb.done();
        break;
    }