MongoDB Linked List

Небольшой этюд на тему связного списка в MongoDB. Приведенный ниже код на мой взгляд показывает, что использование этой структуры данных в MongoDB - не самая лучшая идея. Правда предложенный мной "альтернативный" вариант мне тоже не особенно нравится, но сегодня я просто не знаю "тру" решения.

Для того, чтобы понять о чем речь, создаем файл по имени app.js следующего содержания:

var llist = {
  collectionName: 'llist',
  listId: 0,
  populate: function(n, listId) {
    n = n || 5;
    this.listId = listId || 0;
    db[this.collectionName].remove({list: this.listId});
    var i = n;
    while (i--) {
      this.push({});
    }
    db[this.collectionName].createIndex({next: -1});
    db[this.collectionName].createIndex({list: -1, next: -1});
    return 'Populated ' + n + ' items into <' + this.collectionName + '> collection';
  },
  push: function(obj) {
    obj = obj || {};
    obj._id = new ObjectId();
    obj.list = this.listId;
    obj.next = null;
    var bulk = db[this.collectionName].initializeOrderedBulkOp();
    bulk.find({list: this.listId, next: null}).update({$set: {next: obj._id}});
    bulk.insert(obj);
    return bulk.execute();
  },
  pull: function(id) {
    if (id === undefined) return;
    var obj = db[this.collectionName].findOne({_id: id});
    if (!obj) return;
    var bulk = db[this.collectionName].initializeUnorderedBulkOp();
    bulk.find({_id: id}).removeOne();
    bulk.find({next: id}).updateOne({$set: {next: obj.next}});
    return bulk.execute();
  },
  move: function(id, nextId) {
    if (id === undefined) return;
    var obj = db[this.collectionName].findOne({_id: id});
    if (!obj || obj._id === nextId || obj.next === nextId) return;
    if (nextId === undefined) nextId = null;
    var bulk = db[this.collectionName].initializeOrderedBulkOp();
    bulk.find({next: id}).updateOne({$set: {next: obj.next}});
    bulk.find({next: nextId}).updateOne({$set: {next: obj._id}});
    bulk.find({_id: id}).updateOne({$set: {next: nextId}});
    return bulk.execute();
  },
  find: function() {
    var self = this;
    return (function find(id, arr) {
      var doc = db[self.collectionName].findOne({list: self.listId, next: id});
      if (!doc) return arr;
      arr.push(doc);
      return find(doc._id, arr);
    })(null, []);
  },
  test: function(n) {
    if (!n) n = 10000;
    var ts = Date.now();
    print(this.populate(n));
    print('Time: ' + (Date.now() - ts) + ' ms');
    var arr = [];
    ts = Date.now();
    var arr = this.find();
    print('Found ' + arr.length + ' items');
    print('Time: ' + (Date.now() - ts) + ' ms');
    var firstId = db[this.collectionName].find({list: this.listId}).sort({_id: 1}).limit(1).next()._id;
    var lastId = db[this.collectionName].findOne({list: this.listId, next: null})._id;
    ts = Date.now();
    this.move(lastId, firstId);
    print('Item moved thru ' + --n + ' items');
    print('Time: ' + (Date.now() - ts) + ' ms');
  }
};
 
var list = {
  collectionName: 'list',
  listId: 0,
  dataCollectionName: 'listdata',
  populate: function(n, listId) {
    n = n || 5;
    this.listId = listId || 0;
    db[this.collectionName].remove({list: this.listId});
    db.collection[this.dataCollectionName].remove({_id: this.listId});
    var i = n;
    while (i--) {
      this.push();
    }
    db[this.collectionName].createIndex({list: -1});
    db[this.collectionName].createIndex({list: -1, index: -1});
    return 'Populated ' + n + ' items into <' + this.collectionName + '> collection';
  },
  push: function() {
    var data = db.collection[this.dataCollectionName].findAndModify({query: {_id: this.listId}, update: {$inc: {length: 1}}, upsert: true, new: true});
    return db[this.collectionName].insert({list: this.listId, index: data.length - 1});
  },
  pull: function(index) {
    db.collection[this.dataCollectionName].findAndModify({query: {_id: this.listId}, update: {$inc: {length: -1}}});
    var bulk = db[this.collectionName].initializeOrderedBulkOp();
    bulk.find({list: this.listId, index: index}).removeOne();
    bulk.find({list: this.listId, index: {$gt: index}}).update({$inc: {index: -1}});
    return bulk.execute();
  },
  move: function(index, newIndex) {
    var obj = db[this.collectionName].findOne({list: this.listId, index: index});
    if (!obj || index === newIndex) return;
    var bulk = db[this.collectionName].initializeOrderedBulkOp();
    if (index < newIndex) {
      bulk.find({list: this.listId, index: {$lte: newIndex, $gt: index}}).update({$inc: {index: -1}});
    } else {
      bulk.find({list: this.listId, index: {$gte: newIndex, $lt: index}}).update({$inc: {index: 1}});
    }
    bulk.find({_id: obj._id}).updateOne({$set: {index: newIndex}});
    return bulk.execute();
  },
  find: function() {
    return db[this.collectionName].find({list: this.listId}, {list: 0}).sort({index: -1});
  },
  test: function(n) {
    if (!n) n = 10000;
    var ts = Date.now();
    print(this.populate(n));
    print('Time: ' + (Date.now() - ts) + ' ms');
    var arr = [];
    ts = Date.now();
    this.find().forEach(function(item) {
      arr.push(item);
    });
    print('Found ' + arr.length + ' items');
    print('Time: ' + (Date.now() - ts) + ' ms');
    ts = Date.now();
    this.move(--n, 0);
    print('Item moved thru ' + n + ' items');
    print('Time: ' + (Date.now() - ts) + ' ms');
  }
};

Запускаем MongoDB Shell, загружаем созданный выше файл (load('app.js')) и выполняем тест связного списка (llist.test()) и "альтернативного" варианта (list.test()):

Создание 10000 документов прошло примерно с одинаковой скоростью, в поиске этих самых документов связный список разумеется проиграл, т.к. здесь пришлось выполнить не меньше 10000 запросов к базе данных, а вот с перемещением документа из начала списка в конец связный список ожидаемо опередил мой "альтернативный" вариант, т.к. в этом случае пришлось инкрементить значение поля по имени index у всех документов.

И все же по моему связный список - вообще не вариант. Затестить 100000 документов со связным списком мне так и не удалось, честно говоря не прокатило даже 20000 документов, наверное из-за рекурсии, а вот "альтернативному" варианту потребовалось 857 мс. на поиск 100000 документов и 5210 мс. на инкремент поля index у всех документов:

Точно не самый плохой вариант, может и не самый хороший, но лучше я сегодня не знаю.