algorithm - mongodbの配列操作のアルゴリズムの複雑さ

Question

Mongodbは、$pushや$popなどの多くの便利な配列操作をサポートしていますが、アルゴリズムの複雑さや、実行時の複雑さを把握するための実装方法に関する情報が見つからないようです。どんな助けでも大歓迎です。

Answer 1

I think when it comes to Mongo updates, there are only three relevant cases:

1) an in-place atomic update. For example just increment an integer. This is very fast.

2) an in-place replace. The whole document has to be rewritten, but it still fits into the current space (it shrank or there is enough padding).

3) a document migration. You have to write the document to a new location.

In addition to that there is the cost of updating affected indexes (all, if the whole thing had to be moved).

What you actually do inside of the document (push around an array, add a field) should not have any significant impact on the total cost of the operation, which seem to depend mostly linearly on the size of the document (network and disk transfer costs).

Answer 2

Here's where they are implemented. You can figure out the complexity from there.

This is the $pop operator, for example (this seems like O(N) to me):

    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;
    }