Индексирование базы данных

← →
Serg1981 © (2005-08-03 21:04) [0]

Привет всем ! Как известно, индексы в БД строят для ускорения поиска. А в чём физический смысл индексов, как они строятся, по какому принципу ? Просто создаю БД своего формата и хочу в ней строить индексы самостоятельно. Подскажите что-нибудь, или где можно почитать про это ? Заранее спасибо.

← →
DrPass © (2005-08-03 21:20) [1]

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

← →
Piter © (2005-08-03 22:16) [2]

DrPass © (03.08.05 21:20) [1]
значение поля - положение записи в таблице

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

← →
Джо © (2005-08-03 22:29) [3]

> [2] Piter © (03.08.05 22:16)
> DrPass © (03.08.05 21:20) [1]
> значение поля - положение записи в таблице
> что за бред.

В простейшем случае, индекс - это и есть пары значений: поле-ссылка на него в таблице.

← →
wicked © (2005-08-03 23:11) [4]

> Джо © (03.08.05 22:29) [3]

> В простейшем случае, индекс - это и есть пары значений:
> поле-ссылка на него в таблице.

имхо, в простейшем случае индекс - это массив указателей на записи, отсортированный определенным образом... я бы так делал... :-P

← →
DrPass © (2005-08-03 23:29) [5]

> Piter © (03.08.05 22:16) [2]

Если в таблице одно поле - любой индекс будет занимать как база данных. Кроме того, абсолютно нормальной является ситуация, когда индексы занимают в несколько раз больше места, чем данные. Их задача - ускорить поиск, а не экономить место на диске

← →
Serg1981 © (2005-08-03 23:42) [6]

> имхо, в простейшем случае индекс - это массив указателей
> на записи, отсортированный определенным образом

Допустим, я перечислю, что фамилия ИВАНОВ есть в записях 1, 3, 7 и 28. При попытке найти ИВАНОВА я сразу выдам на экран эти записи. Но если пользователь захочет искать часть фамилии, например, ИВАНО, такого индекса у меня не будет, придётся опять пробегать по всем записям ?

← →
DrPass © (2005-08-03 23:54) [7]

Ну-с, молодой человек, если вы сели за компьютер не в Doom3 бегать, а программы писать - тренируйте логическое мышление. Без него никак...

← →
Serg1981 © (2005-08-03 23:57) [8]

Ну не писать же индекс на каждую букву в отдельности.

P.S. а в игры я не играл никогда, тем более в компьютерные.

← →
DrPass © (2005-08-04 00:09) [9]

Ну это же так просто - расположить слова в индексе в алфавитном порядке, и искать не по полному совпадению, а по подобию.

← →
Джо © (2005-08-04 01:07) [10]

Малехо ликбеза для автора топика и (персонально) для Piter"а ;-)

Индекс - это дополнительная внутренняя таблица Microsoft Access, состоящая всего из двух столбцов: в первом содержатся значения полей, включенных в индекс, а во втором - местоположение этих полей в индексируемой таблице
читать: http://biology.krc.karelia.ru/misc/access/page6.htm.

← →
Lamer@fools.ua © (2005-08-04 07:38) [11]

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

← →
Verg © (2005-08-04 08:26) [12]

если пользователь захочет искать часть фамилии, например, ИВАНО, такого индекса у меня не будет, придётся опять пробегать по всем записям ?

Зачем же по всем. Индексные записи отсортированы по значению ключевого поля. В данном случае - фамилия. При поиске ты должен по обычному алгоритму (бинарный поиск) определить место в индексной таблице, которое должена была бы занять запись, если бы значение поля "фамилия" имело искомое значение. Если искомая фамилия задана неполностью("ивано"), то ты найдешь позицию в индексе (i), где все "иванов", "иванова" и т.д. распологаются строго ниже (иногда эту операцию называют FindNearest). Осталось пройтись вниз по индексу и выдать в качестве результата все записи со значением поля начинающимся на "ивано".
Надо так же проверить i-1 индекс, на предмет точного равенства с "ивано".

← →
Думкин © (2005-08-04 08:47) [13]

> [12] Verg © (04.08.05 08:26)

Это если начало. А если кончало или середка также? Про это он и спрашивает.

← →
Sergey13 © (2005-08-04 09:18) [14]

2 Serg1981 © (03.08.05 21:04)
Странное желание - не зная про индексы писАть свою БД.
ИМХО.

← →
Holy © (2005-08-04 09:28) [15]

> Думкин © (04.08.05 08:47) [13]

ИМХО почти тоже самое... Допустим надо найти ?ивано, т.е. ивано со второй буквы. В пределах одинаковой первой буквы задача сводится к > Verg © (04.08.05 08:26) [12]
Для большего количества букв больще отрежем...

← →
Holy © (2005-08-04 09:32) [16]

> Для большего количества букв больще отрежем...

Читать Для большего количества букв больше отрежем... Т.е. не сравнение с первого символа записи, а убираем эн первых букв.

А вообще согласен с тем, что индексирование это наука...

← →
Sergey13 © (2005-08-04 09:35) [17]

Вообще-то в уже написанных БД, при поиске по %ивано индекс не используется, насколько я знаю. Идет полный перебор.

← →
Думкин © (2005-08-04 09:38) [18]

> [17] Sergey13 © (04.08.05 09:35)

Вот и я про тоже.

← →
Nikolay M. © (2005-08-04 09:56) [19]

Про индексы в MS SQL есть отличнейшая статья
http://www.sql.ru/articles/mssql/03013101Indexes.shtml
БОльшая часть написанного относится к индексам вообще, а не только применительно к MS SQL.

← →
Desdechado © (2005-08-04 11:01) [20]

Serg1981 © (03.08.05 23:57) [8]
> в игры я не играл никогда
тяжелое у тебя детство было...
у некоторых игрушки деревянные, а у тебя вообще никаких...

← →
Serg1981 © (2005-08-04 11:49) [21]

to Nikolay M. © (04.08.05 09:56) [19] :
Большое спасибо !

to Desdechado © (04.08.05 11:01) [20] :
Детство у меня было нормальным, на вкус и цвет товарищей нет. А если нечего сказать по существу темы, то лучше помолчать.

← →
Digitman © (2005-08-04 12:41) [22]

> в чём физический смысл индексов

индекс есть упорядоченный (по тому или иному критерию) список, каждый элемент которого есть некая "ссылка" на "местоположение" индексируемого данным индексным элементом некоего сопоставленного с ним элемента индексируемого списка

простой пример, ч.н. "на огурцах" :

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

BBBB <CRLF>
AAA <CRLF>
ZZZZZ <CRLF>
XX <CRLF>
DDDD <CRLF>
FFFFFF <EOF>

начало каждой из этих строк в этом файле имеет строго определенное смещение (в байтах) отн-но начала файла :

BBBB (+0)
AAA (+6)
ZZZZZ (+11)
XX (+18)
DDDD (+22)
FFFFFF (+28)

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

AAA
BBBB
DDDD
FFFFFF
XX
ZZZZZ

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

чтение файла - это, в конечном итоге, множественные обращения к файловому носителю, которые в любом случае не могут быть выполнены мгновенно (например, в случае с HDD некое обращение к носителю вызывает позиционирование считывающего механизма носителя, и это позиционирование далеко не мгновенное), и чем больше обращений к носителю, тем больше суммарное время, затраченное системой на чтение файла

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

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

тут же возникает вопрос - если "накладные расходы" неизбежны, нельзя ли их как-то минимизировать ?

ответ - можно !

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

для этого упомянутому файлу со строками создается и ставится в однозначное соответствие структурированный индексный файл следующего вида :

+06 "AAA "
+00 "BBBB "
+22 "DDDD "
+28 "FFFFFF"
+18 "XX "
+11 "ZZZZZ "

в этом файле оригинальные строковые значения УЖЕ упорядочены по требуемому критерию

прочитав (поблочно или целиком) этот индексный файл, можно в цикле по прочитанным оттуда структурам брать значение смещения очер.записи, позиционировать механизм носителя и тут же считывать значение строки в ориг.файле - на каждой итерации цикла будет прочитана строка УЖЕ в требуемом порядке сортировки.

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

вот еще простой наглядный пример :

TQuery.ParamByName() - метод-ф-ция, ищущая и возвращающая объект-параметр в списке объектов-параметров по имени искомого параметра, предположим - действует "тупым" итеративным перебором каждого эл-та списка на предмет совпадения имени параметра с заданным

в то же время TQuery.Params[индекс] позволяет получить доступ к искомому объекту не по его имени , а по его "номеру" (индексу) в списке объектов-параметров... при этом позиционирование в списке не требует каких-либо весомых затрат, как в случае проверки каждого имени на совпадение - размер элемента списка умножается на индексный номер элемента, к полученному произведению прибавляется адрес начала списка, результат есть готовая ТОЧНАЯ позиция элемента в списке(безо всяких циклов последовательного чтения/сравнения эл-тов списка, что потребовало бы ощутимо большее время)

← →
Desdechado © (2005-08-04 16:18) [23]

Serg1981 © (04.08.05 11:49) [21]
> Детство у меня было нормальным
Выходит, у остальных оно было того, э-э ... ненормальным? Ведь дети ВСЕГДА играют. И рос ты среди других нормальных неиграющих детей? Не верю! (с)

> на вкус и цвет товарищей нет.
Эт точно! (с)

> А если нечего сказать по существу темы, то лучше помолчать.
Тема же в "Потрепаться", а не в "Базах". Там бы я тебе по существу ответил, а здесь треплюсь :)
Мое право.

← →
TUser © (2005-08-04 17:07) [24]

> Вообще-то в уже написанных БД, при поиске по %ивано индекс не используется, насколько я знаю. Идет полный перебор.

Реализован поиск последовательностей, похожих на образец в генетических базах данных. Хеширование - по совпадению каждой 11-й буквы. Правда, там длина последовательности посолиднее.

← →
oldman © (2005-08-04 17:10) [25]

> Serg1981 © (03.08.05 21:04)
> Просто создаю БД своего формата...

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

Без обид...

← →
Sergey13 © (2005-08-04 17:11) [26]

2[24] TUser © (04.08.05 17:07)
> в генетических базах данных.
А что это? РСУБД с данными по генетике или что другое?

to oldman:

Против всех существующих "заводских" БД есть отмычки и средства взлома.

> А что это?

Банки известных последовательностей ДНК и белков. Например, вот тут лежит геном человека
http://www.ncbi.nlm.nih.gov/genome/guide/human/

to Sergey13 [28] :

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

>А в чём физический смысл индексов

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

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

Всё бы хорошо, но база уже порядка 600 МБайт и это не предел, а на сервере у меня 512 Мб оперативной памяти :(

> programania © (04.08.05 20:21) [31]
ну страхов вы понаписывали...
судя по вашим словам, FoxPro никогда бы не смог проиндексировать таблицу с сотнями тысяч-миллионами записей... однако, он это делал... :-/

programania © (04.08.05 20:21) [31]
А индексы только для сортировки используются, по-вашему? Вы бы, мягко говоря, не выражались так категорично насчет "проще обойтись без индексов"

>wicked © (04.08.05 21:02) [33]
>ну страхов вы понаписывали...
какие слова вас так испугали?

>судя по вашим словам, FoxPro никогда бы не смог проиндексировать таблицу
по каким словам?

> Petr V. Abramov © (04.08.05 21:38) [34]
> А индексы только для сортировки используются, по-вашему?
...отсортировать и быстро в нем искать. [31]
сортировка индексов как раз и служит для быстрого поиска

>Вы бы, мягко говоря, не выражались так категорично насчет "проще обойтись без индексов"
я же обьяснил когда проще и почему, разве это категорично?
или вы считаете что самому создать и поддерживать индексы просто?
ведь именно это собрался делать автор темы.
>хочу в ней строить индексы самостоятельно [1]

> чем больше память тем меньше потребность в индексах

С чего это вдруг?
> большинство файлов полностью входит в память и сортируется
> за секунды

А это?
> проще обойтись без индексов ведь индексы кроме создания
> нужно поддерживать, то есть делать все вставки и удаления
> как и в данных
> и чтоб при этом их не переписывать нужно B-дерево а это
> сложно

Чаще всего операций вставки/удаления производятся намного реже, чем выборки. Так что все эти сложности лучше "перетерпеть". Хотя, конечно, это зависит от поставленных перед СУБД целей. Телефонный справочник на 500 записей будет прекрасно работать и без индексов

> programania © (04.08.05 22:05) [35]
> сортировка индексов как раз и служит для быстрого поиска
Никто их не сортирует, сортируют выборку из таблиц. Иногда индекс этому помогает

> или вы считаете что самому создать и поддерживать индексы просто?
Не просто. Но это не значит, что для приемлемого функционала СУБД они не нужны. Даже если паче чаяния вся таблица влезает в память.

>DrPass © (04.08.05 23:53) [36]
>> чем больше память тем меньше потребность в индексах
>С чего это вдруг?
>Телефонный справочник на 500 записей будет прекрасно работать и без индексов
А при достаточно большой памяти вы будете правы и для 500 000 уловили связь?

> большинство файлов полностью входит в память и сортируется
> за секунды
>А это?
А это из личного опыта
Вот сейчас посмотрел базу на работе
из 1123 файлов db только 11 или 1% больше 10мб а самый большой 66 мб
и для такой мелочи возиться с индексами?

>Чаще всего операций вставки/удаления производятся намного реже, чем выборки.
Да хоть 1 раз все равно придется делать все полностью а не терпеть.

>Petr V. Abramov © (05.08.05 00:30) [37]
> Никто их не сортирует, сортируют выборку из таблиц. Иногда индекс этому помогает

НеОтсортированные индексы теряют смысл
а сортируются они в процессе создания обычно путем заполнения B-дерева
это всего лишь один из методов сортировки

>Но это не значит, что для приемлемого функционала СУБД они не нужны.
Это значит что вы без индексов никогда не работали?
а я этим занимался 20 лет причем при свободной памяти < 500Кбайт
и приемлемом функционале

>Serg1981 © (04.08.05 20:41) [32]
>Всё бы хорошо, но база уже порядка 600 МБайт и это не предел, а на сервере у меня 512 Мб оперативной памяти :(

Не знаю ваших деталей и не буду говорить категорично но мягко говоря
даже в этом случае можно без индексов
Новые записи писать в дополнительный файл и держать его в памяти
В конце дня/месяца сортировать и сливать с основным по ключу за 1-2 минуты
При запросе по ключу в новых записях быстро искать пусть даже последовательно
ведь их немного и они в памяти, а основной файл всегда будет отсортирован
и запросы по ключу будут быстро выполняться двоичным поиском
не говоря уже о обработке всего файла например для создания отчетов
или выборки по выражениям тут разница будет в десятки раз
т.к. без индексов такая обработка займет время последовательного чтения файла
600мб/(10..40мб в сек)<=1 минуты, проверил фильм 690мб читается 43сек
причем дефрагментацию никогда не делал, а с индексами
придется читать файл в случайном порядке по 1 записи,
страшно подумать сколько это займет и жалко диск испытывать.

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

Индексирование базы данных Найти похожие ветки