我想创建一个具有特定顺序的数据库(我正在使用 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 个对象。可以将更改表示为一个更新的对象,并通过一些逻辑来确定需要更新哪些其他对象。这是可行的,但我想知道是否有比这更好的方法。有没有更简单的方法来跟踪任意列表的顺序?
最佳答案
好的,您的链表方式比多重更新方法更快且更具可扩展性,但集合大小为 500,我每次“移动”大约需要 7 毫秒(使用我的基准代码 - 显然不同大小的集合可能会有所作为)。此外,如果您希望能够在服务器上对集合进行排序,则使用“order”值来索引/排序将使其变得容易得多。随着集合大小的增加,多重更新方法平均会相应增加,这是有道理的,因为它大约为 O(n)。无论大小如何,您的方法都保持相当一致,每次移动 0.8 毫秒,这也是有道理的,因为它是 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
关于mongodb - 数据库/集合任意但特定的顺序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9051690/