Объясните мне на пальцах про индексы

← →
leonidus © (2005-09-13 15:58) [0]

Начал изучать теорию реляционных баз данных, разобрался с первичным ключом, но вот теперь встал вопрос про индексы - по простому что это и как они ускоряют поиск?

← →
Sergey13 © (2005-09-13 16:00) [1]

>Объясните мне на пальцах про индексы
Пальцев не хватит. Читать надо.

← →
Reindeer Moss Eater © (2005-09-13 16:02) [2]

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

← →
leonidus © (2005-09-13 16:03) [3]

> Они ускоряют поиск потому, что уменьшают объем данных в
> которых этот поиск производится.

в общем понятно, но какова технология уменьшения объема данных?
неужели по простому никак не объяснить?

← →
Reindeer Moss Eater © (2005-09-13 16:06) [4]

Ищем человеков с фамилией на "A".
Так как индекс содержит упорядоченные значения ключей, то дойдя до первого человека с фамилией на "Б", становится ясно, что поиск можно прекращать. Хотя впереди еще миллион непрочитанных записей.

← →
Anatoly Podgoretsky © (2005-09-13 16:07) [5]

Reindeer Moss Eater © (13.09.05 16:02) [2]
Неправда

← →
Reindeer Moss Eater © (2005-09-13 16:08) [6]

Зато понятно

← →
Anatoly Podgoretsky © (2005-09-13 16:11) [7]

То то же

← →
leonidus © (2005-09-13 16:13) [8]

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

← →
Calm © (2005-09-13 16:16) [9]

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

Ну примерно так.

>>а если там данные не поддающиеся упорядочению, то индекся не дадут результата?

По таким полям индексы не строятся. Например, БЛОБы.

← →
Reindeer Moss Eater © (2005-09-13 16:19) [10]

>а если там данные не поддающиеся упорядочению

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

← →
leonidus © (2005-09-13 16:22) [11]

ок, теперь понятно большое спасибо!
ключи и индексы в общем случае между собой ничего в таком случаем общено не имеют и используются для разных целей?
а для чего вторичные и внешние ключи применяются?

← →
Anatoly Podgoretsky © (2005-09-13 16:24) [12]

leonidus © (13.09.05 16:22) [11]
Ключ частный случай индекса, особое назначение, побочные эффекты.

← →
Anatoly Podgoretsky © (2005-09-13 16:26) [13]

Какой встречный вопрос задавать - помогите, не работает

← →
msguns © (2005-09-13 16:35) [14]

Для каждого индекса СУБД создает дополнительный массив записей на диске, куда помещает для каждой записи таблицы значение поля, по которому строится индекс, и указатель на лог.адрес записи в таблице (лог.адрес - это смещение адресуемой записи от начала табличного файла или секции(страницы), отведенной для таблицы, если вся база в одном файле, по которому легко вычислить физ. адрес в формате BBCCHHHHRRRR). Когда выполняется поиск по данному полю, просматривается не сама таблица, а этот индекс, который, как правило, считывается в ОП полностью либо крупными "пачками". И только после того, как будет выбрано искомое множество, по лог.адресам, хранимым в записях индекса, выполняется собственно считывание из самой таблицы всей записи либо указанных полей. Если индекс по полю, "вес" (фактическая длина в байтах) которого в общей структуре таблицы невелик, а самих записей в таблице много и вариантов значений полей также множество, то такой индекс способен ускорить поиск в сотни, а иногда тысячи и более раз.

Вот почему не стоит заводить индексы по длинным текстовым полям в таблицах, где такое поле составляет более 20-30% от общей длины записи. Такой индекс мало повлияет на скорость выборок (а иногда может даже замедлить) , а места на диске скушает немало. К тому же не надо забывать о том, что фактически при любой можификации таблицы перестраиваются все индексы, что ведет к перезаписи больших кусков или даже всего файла, что в свою очередь может привести к значительной фрагментации. В результате через некоторое время работа с такой таблицей начинает существенно тормозиться.

Кроме того, не рекомендуется индексировать поля типа float из-за неточности сравнений иррациональных чисел.
Очень часто приходилось сталкиваться с горе-программистами, которые сплошной индексацией пытались ускорить работу с изначально неграмотно спроектированными структурно базами данных. Прежде чем активно использовать индексацию, рекомендую почитать что-нибудь про нормализацию, избыточность и целостность. Это - основы БД.

← →
Anatoly Podgoretsky © (2005-09-13 16:42) [15]

Anatoly Podgoretsky © (13.09.05 16:26) [13]
Не в ту ветку. Не обращать внимания.

← →
Anatoly Podgoretsky © (2005-09-13 16:45) [16]

msguns © (13.09.05 16:35) [14]
Если не обращать внимание на частные случаи, такие как кластерные индексы (физически отсутствует) и покрывабщую выборку (может не быть обращения к данныи, например MS SQL).

← →
msguns © (2005-09-13 16:49) [17]

>leonidus © (13.09.05 16:22) [11]
>ключи и индексы в общем случае между собой ничего в таком случаем общено не имеют и используются для разных целей?

Неверно.
Механизм поиска, используемый движками, фактически идентичен и для ключей, и для индексов. Поэтому часто ключи тоже называют индексами, хотя семантически это не совсем одно и то же.
Ключ более "жесток", т.к. не терпит дублирования (хотя и для индекса можно также установить уникальность), кроме того, в качестве первичного ключа обычно используются очень компактные, а потому чрезвычайно эффективные типы данных (Целое, длинное целое), для них у многих СУБД предусмотрен механизм автонаращивания (autoincrement), что позволяет пользователю получать гарантированно уникальные значения при добавлении записей и этим существенно упрощать программирование бизнес-логики серверов или клиентских приложений.

>а для чего вторичные и внешние ключи применяются?

Вторичный ключ - єто фактически тот же индекс, главное назначение которого - ускорение поиска и выборок. Внешние ключи (foreign key) используются для автоматической блокировки сервером удаления или изменения объектов БД, на которых имеются ссылки из других объектов. Классический пример подобной целостности - использование таблиц-справочников, на записи которых имеются ссылки из записей других, не справочных таблиц. Другой пример ссылочной целостности - невозможность удаления записи Мастер-таблицы если у этой записи есть "дочки", т.е. записи-детали в других таблицах.

← →
msguns © (2005-09-13 16:55) [18]

>Anatoly Podgoretsky © (13.09.05 16:45) [16]

Может, еще про кэширование вспомнить ? А оно-то точно по разным схемам делается для разных серверов. Хотя идеи, в основном, одни и те же. Скала, например, создает кучу временных таблиц, интербэйз валит все в версионных страницах, которые по возможности впихивает в память, парадокс вообще все ключи и индексы пхает в отдельные файлы, которые потом и месит, аппетитно пожирая дисковую память, и т.д.

← →
Anatoly Podgoretsky © (2005-09-13 17:01) [19]

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

← →
Ega23 © (2005-09-13 17:18) [20]

На последней КБД практически все предсавители современных СУБД хвастались возможностью индексации БЛОБов в новых версиях своих СУБД.
А ещё на этот счёт кузнецов хороший доклад делал. На www.citforum.ru можно поискать материалы.

← →
Lamer@fools.ua © (2005-09-13 17:31) [21]

По сабджу (на примере MS SQL Server):
http://www.sql.ru/articles/mssql/03013101Indexes.shtml

← →
Андрей Жук © (2005-09-13 17:46) [22]

Индексы к теории РБД отношения не имеют. Они имеют отношение к реализации конкретной СУБД.

← →
Ученик чародея © (2005-09-13 19:30) [23]

>>Sergey13 © (13.09.05 16:00) [1]
>>>Объясните мне на пальцах про индексы
>>Пальцев не хватит. Читать надо.

Пальцы гнуть мы все умеем ;)

>>leonidus © (13.09.05 15:58)

Читай про B-деревья
http://algolist.manual.ru/ds/s_btr.php

← →
Desdechado © (2005-09-13 19:37) [24]

а еще - индексы бывают разные, не только на двоичных деревьях

← →
Anatoly Podgoretsky © (2005-09-13 19:38) [25]

Ega23 © (13.09.05 17:18) [20]
Это наверняка не про индексы, а про пот=лнотекстовый поиск.

← →
Anatoly Podgoretsky © (2005-09-13 19:40) [26]

Desdechado © (13.09.05 19:37) [24]
Вот один такой я и затронул.

← →
Ученик чародея © (2005-09-13 19:42) [27]

>>Desdechado © (13.09.05 19:37) [24]
>>а еще - индексы бывают разные, не только на двоичных деревьях

Только эффективнее В-деревьев пока ничего не создали, хоть алгоритм не относится к простым.

← →
Anatoly Podgoretsky © (2005-09-13 19:47) [28]

Ученик чародея © (13.09.05 19:42) [27]
Ошибаешься, например кластерный, конечно там где он по делу.
Это скорость поиска, выборки и добавления
Не знаю в других базах, кроме MS SQL, есть ли такое чудо. И также покрывающая выборка.

2leonidus
ПМСМ, Андрей Жук © (13.09.05 17:46) [22] - абсолютно прав. Теоретически, индексы не нужны. А вот ключи - даже и в теории нужны и очень.
То, что для ключей приходится строить индексы - не более чем вопрос реализации, как и сами индексы. Если послезавтра ;) будут супер-кванто-туннельные компьтеры и ЗУ - ключи в РСУБД никуда не денутся, а вот индексов может и не быть - например, Некто Нектович внезапно выдумает сверхэффективный метод поиска бех индексов ;).

Всем большое спасибо, очень многое встало на свои места. Сейчас буду разбираться с Join`ами, будут еще вопросы:)

>Андрей Жук © (13.09.05 17:46) [22]
>Индексы к теории РБД отношения не имеют. Они имеют отношение к реализации конкретной СУБД.

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

А теперь вопрос на засыпку, как на пальцах раходратьсяв технологии OLAP?
Я так понял, что ъранилище OLAP формируется на основе обычных реляционных таблиц, но мне не понятна парадигма многомерности данных в OLAP, как двумерные таблицы превращаются в многомерные, и как после этого анализировать полученные данные в гиперкубе? Может ыть кто-то приведет понятный пример скажем для 3-хмерной модели хранилища?

На вопросы меня навела эта статья:
http://www.citforum.ru/database/articles/olap_oltp.shtml

← →
Seg (2005-09-14 14:57) [33]

Таблица всегда остается двухмерной - столбцы и строки.
Просто добавляются служебные столбцы, по которым строятся измерения.

Например есть таблица с полями:

1. Клиент
2. Товар
3. Документ
4. Количество
5. Цена
6. Дата

По этой таблице можно сделать несколько срезов (измерений)
1. Выбрать все количество товара, купленного клинтами
2. Выбрать количество товара, отпущенному по одному документу
3. Выбрать весь проданный товар
4. Сколько товара было продано за день
5. сколько документов было за день
6 сколько клиетов было за день
7 сколько клиентов копило данный вид товара

и т.д.

Получилось 7 измерений. Можно придумать еще столько же.

ну в общем-то понятно, просто уж больно гружено пишут статьи по этому делу

Дошел черед и до Join`ов, в связи с чем появилось два вопроса:
1. Чем же они лучше чем простое условие в Where
2. Чем например left outer join отличается от просто left outer join ? у меня выборка получается одинаковая. в каком случае нужно добавлять outer ?

>Чем например left outer join отличается от просто left outer join
Абсолютно ничем ;)))

2[36] leonidus © (15.09.05 10:58)
1. Они не лучше. Они дают другой результат. В список работников с закрепленными комьпьтерами без джоина не попадут люди без таковых.

Давай уже сразу все вопросы, включая о смысле жизни.

Попутно анекдот:

Купец собирается в дальний путь и спрашивает у дочерей, что им привезти.
Старшая говорит: "Привези мне парчи да шелку на платье",
Средняя: "Мне колье бриллиантовое"
Младшая: "А мне страшное чудище для грязного секса".
- Что ты, доченька, да разве ж так можно !?
- Ладно, папа, пойдем по длинному пути,- привези мне цветочек аленький.

уточняю:
2. Чем например left outer join отличается от просто left join ? у меня выборка получается одинаковая. в каком случае нужно добавлять outer ?

Объясните мне на пальцах про индексы Найти похожие ветки