Почему в MongoDB имеет значение направление индекса?

114

Чтобы процитировать документы :

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

Однако я не вижу причин, по которым направление индекса должно иметь значение для составных индексов. Может кто-нибудь дать дальнейшее объяснение (или пример)?

johndodo
источник

Ответы:

113

MongoDB каким-то образом объединяет составной ключ и использует его как ключ в BTree.

При нахождении отдельных элементов - порядок узлов в дереве не имеет значения.

Если вы возвращаете диапазон узлов - элементы, близкие друг к другу, будут находиться в тех же ветвях дерева. Чем ближе узлы находятся в диапазоне, тем быстрее их можно извлечь.

С одним индексом поля - порядок не имеет значения. Если они расположены близко друг к другу в порядке возрастания, они также будут находиться рядом в порядке убывания.

Когда у вас есть составной ключ - порядок начинает иметь значение.

Например, если ключ - A по возрастанию B по возрастанию, индекс может выглядеть примерно так:

Ряд AB
1 1 1
2 2 6
3 2 7 
4 3 4
5 3 5
6 3 6
7 5 1

Запрос для A по возрастанию B по убыванию должен будет перемещаться по индексу не по порядку, чтобы вернуть строки, и будет медленнее. Например, он вернет Row1, 3, 2, 6, 5, 4, 7

Ранжированный запрос в том же порядке, что и индекс, просто вернет строки последовательно в правильном порядке.

Поиск записи в BTree занимает время O (Log (n)). Поиск диапазона записей по порядку - это только OLog (n) + k, где k - количество возвращаемых записей.

Если записи не в порядке, стоимость может достигать OLog (n) * k

Джаред Келлс
источник
1
Получившаяся строка наверное должна быть 1, 3, 2, 6, 5, 4, 7?
johndodo
Я до сих пор не вижу причин, чтобы это было медленнее. Только алгоритм должен отличаться (для каждой группы значений в A он должен переходить в конец группы и обрабатывать его в обратном порядке), но поскольку индексы MongoDB находятся в памяти, это не должно оказывать заметного влияния на скорость. Кроме того, СУБД ничего не знает о направлении с индексами, и ситуация там очень похожа на афайк?
johndodo
8
Причина снижения производительности в том, что это не просто последовательный список в памяти, как в упрощенном примере. На самом деле это взвешенное дерево. Неудачный прыжок потребует повторного обхода дерева. RDMS окончательно упорядочены по индексам.
Джаред Келлс
1
Получение узлов из BTree по порядку так же просто, как перемещение по каждому листу до тех пор, пока вы не закончите, а затем подняться на уровень вверх и вниз по следующей ветви. Это O (n) Out of order, это намного более интенсивно загружает процессор.
Джаред Келлс
Спасибо за дальнейшие разъяснения. Я проверил документы для индексов MySQL - действительно можно указать направление индекса, но настройка игнорируется.
johndodo
46

Простой ответ , который вы ищете, что направление имеет значение только тогда , когда разбирают на двух или более полей .

Если вы сортируете по {a : 1, b : -1}:

Индекс {a : 1, b : 1}будет медленнее индекса{a : 1, b : -1}

Заид Масуд
источник
1
@MarkPieszak, потому что вся сортировка должна выполняться в памяти, что делает индекс бесполезным
Sammaye
@ Sammaye Я думаю, что это правильная идея, хотя я не уверен, что это все . Я должен был бы посмотреть на реализацию , чтобы знать , как это действительно работает, но я думаю , что результаты могут быть отстранился отсортированы по в одиночку, а затем дополнительные б - то нужно было бы сделать в памяти.
Зайд Масуд
1
хм, странно, в прошлый раз, когда я проверил код, он сбросил частичные сортировки из-за того, как была сортировка, но, может быть, это изменилось
Sammaye
Что делать, если я занимаюсь сортировкой {a: -1, b: -1}, будет ли у меня {a: -1, b: -1}индекс или будет {a: 1, b: 1}достаточно.
Хуссейн
@Hussain в вашем примере {a: 1, b: 1}индекса должно быть достаточно, так как полностью инвертировать индекс можно. например, Индекс {a: 1}можно использовать для сортировки по{a: -1}
Заид Масуд
12

Почему индексы

Поймите два ключевых момента.

  1. Хотя индекс лучше, чем отсутствие индекса, правильный индекс намного лучше любого другого.
  2. MongoDB будет использовать только один индекс для каждого запроса, создавая составные индексы с правильным порядком полей, который вы, вероятно, захотите использовать.

Индексы не бесплатны. Они забирают память и снижают производительность при вставке, обновлении и удалении. Обычно снижение производительности незначительно (особенно по сравнению с увеличением производительности чтения), но это не означает, что мы не можем грамотно создавать индексы.

Как индексы

Определение того, какую группу полей следует проиндексировать вместе, связано с пониманием выполняемых вами запросов. Порядок полей, используемых для создания индекса, имеет решающее значение. Хорошая новость заключается в том, что, если вы сделаете неправильный порядок, индекс вообще не будет использоваться, поэтому его будет легко обнаружить с помощью объяснения.

Почему Сортировка

Вашим запросам может потребоваться сортировка. Но сортировка может быть дорогостоящей операцией, поэтому важно относиться к полям, по которым вы сортируете, как к полю, к которому вы запрашиваете. Так будет быстрее, если у него будет index. Однако есть одно важное отличие: поле, которое вы сортируете, должно быть последним полем в вашем индексе. Единственным исключением из этого правила является то, что если поле также является частью вашего запроса, то правило must-be-last не применяется.

Как Сортировка

Вы можете указать сортировку по всем ключам индекса или по подмножеству; однако ключи сортировки должны быть перечислены в том же порядке, в каком они появляются в указателе. Например, шаблон ключа индекса {a: 1, b: 1} может поддерживать сортировку по {a: 1, b: 1}, но не по {b: 1, a: 1}.

Сортировка должна указывать то же направление сортировки (т. Е. По возрастанию / убыванию) для всех своих ключей, что и шаблон индексного ключа, или указывать обратное направление сортировки для всех своих ключей в качестве шаблона индексного ключа. Например, шаблон ключа индекса {a: 1, b: 1} может поддерживать сортировку по {a: 1, b: 1} и {a: -1, b: -1}, но не по {a: -1 , б: 1}.

Допустим, есть такие индексы:

{ a: 1 }
{ a: 1, b: 1 }
{ a: 1, b: 1, c: 1 }

Example                                                    Index Used
db.data.find().sort( { a: 1 } )                            { a: 1 }
db.data.find().sort( { a: -1 } )                           { a: 1 }
db.data.find().sort( { a: 1, b: 1 } )                      { a: 1, b: 1 }
db.data.find().sort( { a: -1, b: -1 } )                    { a: 1, b: 1 }
db.data.find().sort( { a: 1, b: 1, c: 1 } )                { a: 1, b: 1, c: 1 }
db.data.find( { a: { $gt: 4 } } ).sort( { a: 1, b: 1 } )   { a: 1, b: 1 }
Сомнатх Мулук
источник
Я понимаю, что это пример, но если есть индекс { a: 1, b: 1, c: 1 }, действительно ли вам нужны индексы { a: 1}и / { a: 1, b: 1}или индекс { a: 1, b: 1, c: 1 }охватывает все случаи? Если запросы всегда используют одну и ту же сортировку: 1 без сортировки в запросе с -1
Лукас Лизис
1
Если есть много запросов, которые работают только со свойством 'a', быстрее выполнять поиск по индексу со свойством 'a' для механизма базы данных, чем поиск по индексу с 3 свойствами 'a', 'b', 'c'. Потому что размер индекса будет увеличиваться, и количество тоже увеличивается. напр. Если в книге 20 глав. Так что быстрее перейти к главе 3, а затем к конкретной странице. @LukasLiesis
Somnath