RoSVmentMasterZiv,
O - это что?
какой знак имел ввиду между O и N?

хочешь проверить без индекса

select *
from table
where
index_field = 10

select *
from table
where
index_field + 1 = 11

Holmes48MasterZiv, можешь привести пример своего видения(ускорения индекса)
как я понимаю. допустим в таблице 500000 записей...O(N) будет перебирать все 500000
если мы создаем индекс то по формуле O(logN)двоичный нам потребуется примерно 19 итераций
как у тебя написано мы должны logN/N получается 19/500000 = 3.8*10^-5
Не врублюсь где тут скорость???
Спасибо

это значит что скорость при индексе(а точнее сложность) составляет 3.8*10^-5 * 100% от скорости без индекса.

всё ещо не видишь скорость?

но это сложность поиска, она не учитывает что основное время пойдёт на чтение шдд, перегон страниц памяти и хождение пакетов по сети.. тоесть не стоит ожидать что за тоже время по индексу база сможет найти 100000 строк получив 100 000 запросов.

Holmes48MasterZiv, можешь привести пример своего видения(ускорения индекса)
как я понимаю. допустим в таблице 500000 записей...O(N) будет перебирать все 500000
если мы создаем индекс то по формуле O(logN)двоичный нам потребуется примерно 19 итераций
как у тебя написано мы должны logN/N получается 19/500000 = 3.8*10^-5
Не врублюсь где тут скорость???
Спасибо

тут надо походу обяснить по простому что такое индекс.

вот есть у тебя поле(однобайтовое)
там значения от 0 до 255. и есть поле примари кея - число.



как по нему будет построен индекс.

(мускл не так строит, но на пример)

работаем в 16битном режиме - адреса по файлу ввиде двух байт

тогда создадим файл, читая от начала который сможем реализовать такую логику.

нам надо найти строки с числом (в двоичном виде наш байт...индексного столбца)
0000 0001

запись файла в шестнадцетиричном виде, русские буквы заменяют какието-цифры

0002 аааа
0004 бббб
0006 вввв
0008 гггг
000А дддд
000С ееее
000Е жжжж
0010 зззз

читаем файл индекса
для нашего числа 0000 0001
1)считываем первые 4 байта(0002 аааа), если первый бит(счёт слева направо начиная с 1) ноль, берём первые 2 иначе последние 2
2)переходим в файле по полученому смещению на предыдущем шаге (в нашем случае на 0002
3)читаем опять четыре байта(0004 бббб) - опять берём нужные два но уже по второму биту
- нам надо перейти на 0004
...обработав первые 7 нулей мы дойдём до записи
0010 зззз
так как 8 бит единица, то брать надо адрес зззз

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

тоесть - без индекса, мы пересматриваем весь файл данных по строчно, ищем нужный столбец и смотрим - 1 там или нет

по индексу, попрыгав 8 раз мы попадаем в место, где уже перечислены нужные нам строки.

и будь в таблице 1000 строк, или милиард, если со значением 1 в этом поле в обоих случаях 10 строк, скорей всего время поиска будет практически темже.

да ничего тут не надо учитывать... тебе и написали... сложность задачи

Н и логарифм по основанию 2 от Н

если записей милиард.


без индекса- ты найдёшь её на милиардном шаге(один шаг - просмотр одной записи - оно или нет)

с индексом.
..числа записываються в машине в двоичном виде...

log(1 000 000 000) = x
означает, что 2 возводя в степерь х получим милиард.

lg( 1 000 000 000) = как мы знаем 9, это значит что множества мощьностью милиард и нумерация с нуля ...тоесть максимальное число милиардное по щёту - 999 999 999, нужно 9 знаков(цифр)

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

поиск по индексу - один шаг, обработка одного бита.
итого, нам надо для поиска по индексу сделать х шагов.

вот и всё...

Holmes48alex564657498765453,
я понял твою мысль тут необходимо учитывать кординальность индекса

а кардинальность индекса по простому

поле строковое на 8 символов, индекс на первые 4 (символы однобайтные)

поиск по такому индексу тоже самое что

два поля по 4 байта, составной индекс первое плюс второе но длина индекса 4 байта

или тоже что выше но индекс на все 8 байт, но в секции веар указано только первое поле и третье какоето

или два поля, на одно индекс, а ищем мы в секции веар по одному и другому.

во всех случаях индекс выделяет только часть записей, из которых нужно ещо отфильтровать не нужное.

если сравнивать с совсем без индекса, то да...тут уже ситуация меняеться...

записей опять милиард, два поля по 4 байта, индекс на первое поле, ищем по обоим.

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

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

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