MongoDB sammenkæder den sammensatte nøgle på en eller anden måde og bruger den som nøglen i et BTree.
Når du finder enkelte varer - Rækkefølgen af noderne i træet er irrelevant.
Hvis du returnerer en række noder - Elementerne tæt på hinanden vil være nede i de samme grene af træet. Jo tættere noderne er i området, jo hurtigere kan de hentes.
Med et enkelt feltindeks - Rækkefølgen er ligegyldig. Hvis de er tæt på hinanden i stigende rækkefølge, vil de også være tæt på hinanden i faldende rækkefølge.
Når du har en sammensat nøgle - Rækkefølgen begynder at få betydning.
For eksempel, hvis nøglen er A stigende B stigende, kan indekset se sådan ud:
Row A B 1 1 1 2 2 6 3 2 7 4 3 4 5 3 5 6 3 6 7 5 1
En forespørgsel for A stigende B faldende skal springe rundt i indekset ude af rækkefølge for at returnere rækkerne og vil være langsommere. For eksempel vil det returnere række 1, 3, 2, 6, 5, 4, 7
En intervalforespørgsel i samme rækkefølge som indekset vil blot returnere rækkerne sekventielt i den korrekte rækkefølge.
At finde en post i et BTree tager O(Log(n)) tid. At finde en række poster i rækkefølge er kun OLog(n) + k, hvor k er antallet af poster, der skal returneres.
Hvis posterne er ude af drift, kan omkostningerne være så høje som OLog(n) * k