数据库/集合任意但特定的顺序

Question

我想创建一个具有特定顺序的数据库(我使用的是mongodb)集合，该顺序也可以重新排列。例如，如果我有

[A,B,C,D,E]

我可以把E移到第三个位置，顺序是

[A,B,E,C,D]

我希望尽可能少地更改对象，因此在每个对象上建立索引是不起作用的(因为为了简单的移动，我需要更改所有后续元素的索引)。

我还可以像创建链表一样创建对象，这样每个对象都将具有前一个和下一个对象的id。示例更改将如下所示。

["A":{prev:null, next:"B"},
"B":{prev:"A", next:"C"},
"C":{prev:"B", next:"D"},
"D":{prev:"C", next:"E"},
"E":{prev:"D", next:null}]

将更改为

["A":{prev:null, next:"B"},
"B":{prev:"A", next:"E"},
"C":{prev:"E", next:"D"},
"D":{prev:"C", next:null},
"E":{prev:"B", next:"C"}]

对于任意大小的集合，它最多只能更改5个对象。更改可以表示为一个更新的对象，并具有一些逻辑来确定需要更新的其他对象。这是可行的，但我想知道是否有比这更好的方法。有没有更简单的方法来跟踪任意列表的顺序？

Answer 1

好的，你的链表方法比多重更新方法更快，更具伸缩性，但是当集合大小为500时，我每次“移动”的时间大约是7ms (使用我的基准测试代码--显然不同大小的集合可能会有所不同)。此外，如果您希望能够对服务器上的集合进行排序，使用" order“值对其进行索引/排序将使其更容易。随着集合大小的增加，多重更新方法的平均值也相应增加，这是有意义的，因为它大致为O(n)。您的方法在每次移动0.8ms时保持相当一致，无论大小如何，这也是有意义的，因为它是O(1)。

下面是两个测试的填充代码，它演示了简单的模式设计/索引配置：

var populateMulti = function(colSize) {
   db.test10.drop();
   for(var i=0;i<colSize;i++) {
      db.test10.save({name:""+i, order:i});
   }  
   db.test10.ensureIndex({order:1});
}

var populateLinked = function(colSize) {
   db.test10.drop();
   db.test10.save({name: ""+0, prev:null, next:""+1});
   for(var i=1;i<colSize-1;i++) {
      db.test10.save({name:""+i, prev:""+(i-1), next:""+(i+1)});
   }  
   db.test10.save({name: ""+(colSize-1), prev:""+(i-1), next:null});
   db.test10.ensureIndex({name:1});
}

这是我对这两种情况的移动代码。关于潜在的5个更新，你是对的--我并没有全盘考虑到这一点。

var moveMulti = function(oldPos,newPos) {
   if(oldPos == newPos) return;
   db.test10.update({order:oldPos}, 
                    {$set:{order:newPos, hold:true}}, 
                    false, false);
   if(oldPos < newPos) {
      db.test10.update({order:{$gt:oldPos, $lte:newPos}, hold:{$exists:false}},
                       {$inc:{order:-1}}, 
                       false, true);
   } else if(newPos < oldPos) {
      db.test10.update({order:{$gte:newPos, $lt:oldPos}, hold:{$exists:false}},
                       {$inc:{order:1}}, 
                       false, true);
   }
   db.test10.update({order:newPos}, 
                    {$unset:{hold:1}}, 
                    false, false);
}

var moveLinked = function(oldPos,newPos) {
   var toMove = db.test10.findOne({name:""+oldPos});
   var dest = db.test10.findOne({name:""+newPos});
   if(toMove.prev != null) {
      db.test10.update({name: toMove.prev}, {$set:{next:toMove.next}}, false, false);
   }
   if(toMove.next != null) {
      db.test10.update({name: toMove.next}, {$set:{prev:toMove.prev}}, false, false);
   }
   if(dest.prev != null) {
      db.test10.update({name: dest.prev}, {$set:{next:toMove.name}}, false, false);
   }
   db.test10.update({name: toMove.name}, {$set:{prev:dest.prev, next:dest.name}}, false, false);
   db.test10.update({name: dest.name}, {$set:{prev:toMove.name}}, false, false);
}

我将省略基准测试代码。如果您想自己运行它，可以在这里查看整个过程：https://gist.github.com/1700270

以下是我笔记本电脑上的结果：

coll size: 10; finished 5000 moves with multi-update in: 1188ms; 0.2376ms per move
coll size: 10; finished 5000 moves with linked in: 3593ms; 0.7186ms per move
coll size: 100; finished 5000 moves with multi-update in: 7545ms; 1.509ms per move
coll size: 100; finished 5000 moves with linked in: 3800ms; 0.76ms per move
coll size: 500; finished 5000 moves with multi-update in: 37754ms; 7.5508ms per move
coll size: 500; finished 5000 moves with linked in: 4027ms; 0.8054ms per move
coll size: 1000; finished 5000 moves with multi-update in: 71609ms; 14.3218ms per move
coll size: 1000; finished 5000 moves with linked in: 4221ms; 0.8442ms per move
coll size: 10000; finished 5000 moves with multi-update in: 676043ms; 135.2086ms per move
coll size: 10000; finished 5000 moves with linked in: 4041ms; 0.8082ms per move