MySQL сложность индексации и времени доступа к данным

Question

in MySQL Я читал, что сложность времени доступа к данным, когда у нас индексирование по указанному c столбцу данных log(n) из-за использования BTree, есть ли сценарий, когда время доступа к данным стало больше * 1003? * например O(n), потому что, когда мы вставляем данные в отсортированном виде в дерево BTree, дерево увеличивается в одну сторону, а сложность доступа к данным возрастает до O(n) имеют ли они какую-либо политику для вставки данных в это индексирование BTree ?? спасибо за ответ

Answer 1

Некоторые вещи, на которые следует обратить внимание:

• Доступ к диску гораздо важнее (для производительности), чем O ().
• «Правило большого пальца»: узел имеет 100 sub узлы (или листовые элементы). Следовательно ...
• В типичном InnoDB BTree (данные или индекс) таблица из миллионов строк будет иметь глубину всего около 3 уровней. Для триллионов рядов около 6 уровней. Это основное место, где вступает в игру «log n».
• BTrees, если дополнено снизу вверх, остается сбалансированным.
• В MySQL не беспокойтесь о BTrees; есть и худшие вещи: индексация, формулировка запросов и т. д. c.
• InnoDB использует B+Trees, что делает сканирование индекса достаточно эффективным, так как не нужно детализировать дерево каждый раз, когда оно исчерпывает элементы узла.
• Википедия является еще одной полезной ссылкой.