Изучение BTrees.В частности, деревья B +.
Давайте найдем один элемент по индексу BTree.BTree имеет корневой узел;начать там.Он может содержать около 100 ссылок на подузлы и информацию о диапазоне значений в каждом.Заходите в соответствующий подузел.Для маленького стола, вы закончили.Но для огромного стола вы повторяете процесс несколько раз.(Возможно, 6 итераций для таблицы с триллионами строками.) Готово.Вы нашли одну строку, которую хотели.
Теперь давайте выберем «диапазон» строк.(Пример: WHERE id BETWEEN 1234 and 9876 или WHERE name LIKE 'T%' Выполните вышеописанное, чтобы найти первый из диапазона, затем перейдите к «следующей» записи в нижнем («листовом») узле, в котором вы находитесь. Это нормально, пока вы не исчерпаетезаписей в конечном узле.
Как включается + in B+Tree. Это означает, что есть ссылка от этого узла к «следующему» узлу на нижнем уровне. Так что это довольно быстропродолжить запрос диапазона.
Статистика для таблицы с миллионами строк с разветвлением 100:
Чтобы найти конкретный элемент: 3 узла (блоки по 16 КБ в случаеНужно дотронуться до InnoDB).
Чтобы получить 500 последовательных строк: 3 узла, чтобы добраться до начала, а затем еще около 5 для сканирования вперед.
Сравнить ... Если не было индексавам нужно будет сканировать всю таблицу, содержащую около 10 000 блоков (1M / 100). Это потребуется для любого из приведенных выше гипотетических запросов.
В InnoDB (в MySQL) почти все ключи, которые выкогда-либо сделайте, будет ПЕРВИЧНЫЙ КЛЮЧ, УНИКАЛЬНЫЙ, и ИНДЕКС. Это - деревья B +;(в отличие от других поставщиков).Кроме этого, есть ПРОСТРАНСТВО в FULLTEXT;они более сложные.
Если вы сделаете SHOW CREATE TABLE foo, вы получите некоторую информацию об индексах.`information_schema имеет дополнительную информацию.