How to create a (double) linked list structure in MongoDB?

Question

I'm trying to store a multitude of documents which are double linked i.e. they can have a predecessor and a successor. Since the collection exists of different documents I'm not sure if I can create a feasible index on it:

{"_id": "1234", "title": "Document1", "content":"...", "next": "1236"}
{"_id": "1235", "title": "Document2", "content":"...", "next": "1238"}
{"_id": "1236", "title": "Document1a", "content":"...", "prev": "1234"}
{"_id": "1237", "title": "Document2a", "content":"...", "prev": "1235", "next": "1238"}
{"_id": "1238", "title": "Document2b", "content":"...", "prev": "1237", "next": "1239"}
...

Since I'll need the whole 'history' of a document including prev and next documents I guess I'll have to perform a multitude of querys depending on the size of the list?

Any suggestions on how to create a performant index? A different structure for storing double linked lists would also be interesting.

Answer 1

If you want to optimize reading you can use arrays to store previous and next documents.

{
    "_id": "1237", 
    "title": "Document1", 
    "content":"...", 
    "next": "1238",
    "prev": "1235",
    "parents" : [1000, 1235]
    "children" : [1238, 1239]
}

You can then get all the documents where your _id is either in child or parents array. This solution is good if you only need parents or children of the document. To get a whole list you can't efficiently use indexes with $or and two $in operators.

Alternative and probably a better solution is to store the entire list for each document i.e. child and parents in one array:

{
    "_id": "1237", 
    "title": "Document1", 
    "content":"...", 
    "next": "1238",
    "prev": "1235",
    "list_ids" : [1000, 1235, 1238, 1239, 1237]
}

That way you can have an index on list_ids and get all the documents with a simple $in query that will be fast.

The problem with both of the solutions is that you will need to update all related documents when you add a new document. So this is probably not a good solution if you're going to have a write heavy app.