Was ist der effizienteste Weg, um eine Baumstruktur in MongoDB zu speichern?

Question

Ich dachte, die einfachste Sache eine flache Liste wäre:

{ 
    id: ObjectId() 
    parentId: ObjectId() 
    value: ‘foo’, 
} 

Nur eine große Sammlung. Um die untergeordneten Knoten eines Knotens zu finden, durchsuchen Sie die Liste und suchen Sie alle Instanzen, in denen die parentId der aktuellen Knoten-ID entspricht. Indizes auf ID/ParentId.

Dies könnte für Schreibvorgänge schneller sein, aber Lesevorgänge können ziemlich schrecklich werden. Und wir werden viel mehr lesen als schreiben!

MongoDB hat eine Art von in Baumdatenstruktur aufgebaut: https://docs.mongodb.com/manual/applications/data-models-tree-structures/

Aber ich frage mich, wie das wie das von einer flachen Liste unterscheidet ich vorgeschlagen.

Answer 1

Wenn Sie einen Index für id und einen Index für parentId definieren, sollten die untergeordneten Elemente eines Knotens sehr schnell sein.

Warum denkst du wird es schrecklich sein?

---

UPDATE: Der schlimmste Fall O(log N) sein würde, aber es ist wichtig zu beachten, dass der Eimer Größe Mongo verwendet, ist 8192 (source). Das bedeutet, dass sich eine wirklich kleine Konstante multipliziert, was bedeutet, dass MongoDB-Operationen ziemlich schnell sein können.