|
Способы реализации индексов
|
||
|---|---|---|
Участник
Откуда: ★[msg=16399436]★[msg=20850760]
Сообщения: 13 456 |
||
| 29.03.2011, 10:09 |
|
|
|
|
|
Способы реализации индексов
|
|||
|---|---|---|---|
|
#18+
При поиске/сканировании по индексу в MS SQL данные всегда берутся из индексов, в Firebird индекс содержит ссылку на запись и данные берутся из таблицы. Какие плюсы и минусы у различных способов индексирования и как это реализовано в других СУБД? Вопрос чисто теоретический, надеюсь того кто знает не затруднит просветить в этом плане. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2011, 03:25 |
|
||
|
Способы реализации индексов
|
|||
|---|---|---|---|
|
#18+
Индекс СпособовичПри поиске/сканировании по индексу в MS SQL данные всегда берутся из индексовЯ хоть MS SQL и не знаю, но готов поспорить, что это неверно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2011, 09:54 |
|
||
|
Способы реализации индексов
|
|||
|---|---|---|---|
|
#18+
miksoftИндекс СпособовичПри поиске/сканировании по индексу в MS SQL данные всегда берутся из индексовЯ хоть MS SQL и не знаю, но готов поспорить, что это неверно. Всегда - не верное утверждение, с чего ТС так решил не ясно. Для некластерных индексов обычно вернее даже обратное (если не брать include). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2011, 10:09 |
|
||
|
Способы реализации индексов
|
|||
|---|---|---|---|
|
#18+
Индекс СпособовичКакие плюсы и минусы у различных способов индексирования и как это реализовано в других СУБД? Плюс и минус тут тупо один: скорость работы. Разные индексы работают лучше остальных в разных ситуациях. Поэтому в "других СУБД" есть туева хуча типов индексов и огромные тома документации в которых подробно расписывается в каких случаях какие типы лучше использовать. Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2011, 12:01 |
|
||
|
Способы реализации индексов
|
|||
|---|---|---|---|
|
#18+
kDnZPmiksoftпропущено... Я хоть MS SQL и не знаю, но готов поспорить, что это неверно. Всегда - не верное утверждение, с чего ТС так решил не ясно. Для некластерных индексов обычно вернее даже обратное (если не брать include). Да уточню, не всегда, при Index Seek через Key Lookup будет брать из кластерного/таблицы. При Index Scan всегда, либо вообще не будет использовать индекс. Dimitry SibiryakovИндекс СпособовичКакие плюсы и минусы у различных способов индексирования и как это реализовано в других СУБД? Плюс и минус тут тупо один: скорость работы. Разные индексы работают лучше остальных в разных ситуациях. Поэтому в "других СУБД" есть туева хуча типов индексов и огромные тома документации в которых подробно расписывается в каких случаях какие типы лучше использовать. Это понятно, интересует чуть больше деталей. Интересует обычный B-tree индекс и именно варианты его реализации в различных СУБД. Расскажите хотя бы в первом приближении. Или киньте ссылкой на материал именно по этой теме. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2011, 18:08 |
|
||
|
Способы реализации индексов
|
|||
|---|---|---|---|
|
#18+
Индекс СпособовичИнтересует обычный B-tree индекс и именно варианты его реализации в различных СУБД. Варианты не в реализации, а в том, что именно в индексе хранится. У IB/FB в индексе хранится фактически хэш данных и именно поэтому она всегда лезет за реальными данными в таблицу. Зато поиск по индексу сводится к быстрому сравнению бинарных данных. Это оптимально когда выбирается малое число записей из многих. Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2011, 18:24 |
|
||
|
Способы реализации индексов
|
|||
|---|---|---|---|
|
#18+
On 29.03.2011 10:54, miksoft wrote: > При поиске/сканировании по индексу в MS SQL данные *всегда* берутся из индексов > > Я хоть MS SQL и не знаю, но готов поспорить, что это неверно. Таки неверно. Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2011, 21:33 |
|
||
|
Способы реализации индексов
|
|||
|---|---|---|---|
|
#18+
On 29.03.2011 4:25, Индекс Способович wrote: > При поиске/сканировании по индексу в MS SQL данные всегда берутся из индексов, в > Firebird индекс содержит ссылку на запись и данные берутся из таблицы. Это утверждение неверно. > Какие плюсы и минусы у различных способов индексирования и как это реализовано в > других СУБД? Основной способ индексирования во всех субд -- B+tree. Все остальные виды индексов в общем-то достаточно экзотичны и малоприменимы в общей практике, и призваны лечить какие-то экзотические тупые запросы. Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2011, 21:36 |
|
||
|
Способы реализации индексов
|
|||
|---|---|---|---|
|
#18+
MasterZivOn 29.03.2011 4:25, Индекс Способович wrote: > При поиске/сканировании по индексу в MS SQL данные всегда берутся из индексов, в > Firebird индекс содержит ссылку на запись и данные берутся из таблицы. Это утверждение неверно. > Какие плюсы и минусы у различных способов индексирования и как это реализовано в > других СУБД? Основной способ индексирования во всех субд -- B+tree. Все остальные виды индексов в общем-то достаточно экзотичны и малоприменимы в общей практике, и призваны лечить какие-то экзотические тупые запросы. Прочитайте пожалуйста внимательно мое второе сообщение в теме. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2011, 22:34 |
|
||
|
Способы реализации индексов
|
|||
|---|---|---|---|
|
#18+
Dimitry SibiryakovИндекс СпособовичИнтересует обычный B-tree индекс и именно варианты его реализации в различных СУБД. Варианты не в реализации, а в том, что именно в индексе хранится. У IB/FB в индексе хранится фактически хэш данных и именно поэтому она всегда лезет за реальными данными в таблицу. Зато поиск по индексу сводится к быстрому сравнению бинарных данных. Это оптимально когда выбирается малое число записей из многих. Имеется ввиду, что индекс представляет собой b-дерево с неполными данными? Потому как хэш-данных храниться в хэш-индексах, которые не имеют информации о порядке и отсутствуют в IB/FB. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2011, 23:08 |
|
||
|
Способы реализации индексов
|
|||
|---|---|---|---|
|
#18+
Индекс СпособовичИмеется ввиду, что индекс представляет собой b-дерево с неполными данными? Потому как хэш-данных храниться в хэш-индексах, которые не имеют информации о порядке и отсутствуют в IB/FB. А что такое неполные данные? И почему это хэш-индексы не имеют информации о порядке? Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2011, 23:21 |
|
||
|
Способы реализации индексов
|
|||
|---|---|---|---|
|
#18+
Dimitry SibiryakovИндекс СпособовичИмеется ввиду, что индекс представляет собой b-дерево с неполными данными? Потому как хэш-данных храниться в хэш-индексах, которые не имеют информации о порядке и отсутствуют в IB/FB. А что такое неполные данные? И почему это хэш-индексы не имеют информации о порядке? 1. Меньше чем исходные данные. 2. По определению. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2011, 23:26 |
|
||
|
Способы реализации индексов
|
|||
|---|---|---|---|
|
#18+
Индекс Способович1. Меньше чем исходные данные. 2. По определению. А тебе никогда не приходило в голову, что в качестве хэш-функции можно выбрать, например, toupper() и тем самым получить case-insensitive индекс? При этом оба твоих пункта плачут и идут лесом. Хэши, знаешь ли, не ограничиваются криптографическими... Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2011, 23:29 |
|
||
|
Способы реализации индексов
|
|||
|---|---|---|---|
|
#18+
Dimitry SibiryakovИндекс Способович1. Меньше чем исходные данные. 2. По определению. А тебе никогда не приходило в голову, что в качестве хэш-функции можно выбрать, например, toupper() и тем самым получить case-insensitive индекс? При этом оба твоих пункта плачут и идут лесом. Хэши, знаешь ли, не ограничиваются криптографическими... Если бы определением хэш-функции было - любая функция, вы были бы правы. Но у хэш-функции есть определение и то что вы приводите никак туда не подходит. Собственно как и case-insensitive индекс не подходит под определение хэш-индекса. Но если вы настаиваете, ладно вы правы. Лучше давайте вернемся к теме. К чему вы сказали про хэш данных в индексе? Dimitry SibiryakovВарианты не в реализации, а в том, что именно в индексе хранится. У IB/FB в индексе хранится фактически хэш данных и именно поэтому она всегда лезет за реальными данными в таблицу. Я так понимаю из индекса данные не берутся исключительно из-за отсутствия в них информации об актуальности данных (информации о версиях)? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2011, 23:45 |
|
||
|
Способы реализации индексов
|
|||
|---|---|---|---|
|
#18+
Я сказал это потому, что я не ограничиваю пространство хэш-функций узкими рамками функций, пригодных для криптографических целей. И так да, согласно этому определению любая функция может являться хэш-функцией пока удовлетворяет условию однозначности преобразования x в f(x). Поэтому f(x)=upper(x) или f(x)=x ничем не хуже чем f(x)=md5(x). Даже лучше, поскольку при условии x<y<z выполнение условия f(x)<f(y)<f(z) позволяет получить тот самый индекс, сохраняющий информацию о порядке. И данные из индекса не берутся не только из-за отсутствия информации об их актуальности, но и потому, что данных там, собственно, нет. Применяемая для получения индексного ключа функция в общем случае необратима, что как раз свойственно хэш-функциям. Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.03.2011, 00:07 |
|
||
|
Способы реализации индексов
|
|||
|---|---|---|---|
|
#18+
Dimitry SibiryakovЯ сказал это потому, что я не ограничиваю пространство хэш-функций узкими рамками функций, пригодных для криптографических целей. И так да, согласно этому определению любая функция может являться хэш-функцией пока удовлетворяет условию однозначности преобразования x в f(x). Поэтому f(x)=upper(x) или f(x)=x ничем не хуже чем f(x)=md5(x). Даже лучше, поскольку при условии x<y<z выполнение условия f(x)<f(y)<f(z) позволяет получить тот самый индекс, сохраняющий информацию о порядке. И данные из индекса не берутся не только из-за отсутствия информации об их актуальности, но и потому, что данных там, собственно, нет. Применяемая для получения индексного ключа функция в общем случае необратима, что как раз свойственно хэш-функциям. ZXY<Zxy<abc и ZXY<ZXY<ABC ) Это называется коллизии, они так же не позволяют сохранять порядок. Если не ограничивать пространство арбузов узкими рамками тыквины, а ещё и яблоки арбузами называть. Я не настаиваю, но я бы предпочел называть функции подходящие под определение хэш-функции. Но не верьте мне, я просто беру частные случаи, на самом деле вы правы. Кстати, а как в Oracle с этим дело обстоит, там данные берутся из индекса? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.03.2011, 00:45 |
|
||
|
Способы реализации индексов
|
|||
|---|---|---|---|
|
#18+
Индекс СпособовичКстати, а как в Oracle с этим дело обстоит, там данные берутся из индекса? в B+Tree индексе данных нет. Есть только ссылки на данные, о чем и говорит DS. MS SQL (как и любой другой блокировочный сервер, и если в MS SQL не включать версионность) может использовать только индекс (без данных) по столбцу field например для count(field), потому что число ключей всегда соответствует числу записей. То же самое - если и поиск и выборка идет только одного индексного столбца, тут в данные лазить без надобности. У ФБ по причине версионности это не так. Например, у трех версий одной записи может быть 2 ключа. Т.е. количество ключей может быть больше чем количество записей, но не меньше чем количество версий. И, в ключах индексов ФБ не хранится информация о транзакции. Таким образом, без чтения версии и определения ее видимости нельзя посчитать count по столбцу. Dmitry Sibiryakov косвенно намекает на общее сходство обычных индексов ФБ с индексами по выражению, которые уж точно самих данных не содержат, хотя выражение может быть A+0, т.е. даже не меняющее значения столбца. При всем при этом индексы ФБ - достаточно обычные B+деревья, с некоторой спецификой, правда, куда входит как минимум префиксная компрессия и однонаправленность скана ключей. Данные в индексах - это как раз кластерные индексы, или, грубо говоря, таблица, отсортированная по "индексному" столбцу. Коллеги вполне могут меня поправить, я глубоко устройством кластерных индексов не интересовался. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.03.2011, 03:54 |
|
||
|
Способы реализации индексов
|
|||
|---|---|---|---|
|
#18+
kdv, kdv... Например, у трех версий одной записи может быть 2 ключа . Т.е. количество ключей может быть больше чем количество записей, но не меньше чем количество версий . ... Сначала ключей меньше чем версий, потом обратное: ключей не может быть меньше чем версий. Где описка? :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.03.2011, 07:44 |
|
||
|
Способы реализации индексов
|
|||
|---|---|---|---|
|
#18+
kdvУ ФБ по причине версионности ... в B+Tree индексе данных нет. Я правильно понимаю, что в ФБ хранение в индексе хэша, а не данных Вы объясняете версионностью? Dimitry SibiryakovУ IB/FB в индексе хранится фактически хэш данных и именно поэтому она всегда лезет за реальными данными в таблицу. Зато поиск по индексу сводится к быстрому сравнению бинарных данных. Это оптимально когда выбирается малое число записей из многих. Я правильно понимаю, что такие понятия как covered indexes и indexes with included columns (которые позволяют снизить издержки на IO и "экономить" буфферный кэш) в IB/FB отсутвуют как класс? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.03.2011, 08:46 |
|
||
|
Способы реализации индексов
|
|||
|---|---|---|---|
|
#18+
Sk1N.Сначала ключей меньше чем версий, потом обратное: ключей не может быть меньше чем версий. Где описка? :) ошибка во второй части. количество записей <= количество ключей <= количество записей+версий pkarklinЯ правильно понимаю, что в ФБ хранение в индексе хэша, а не данных Вы объясняете версионностью? нет. И про "хэш в индексе" Сибиряков уже объяснил, что ОН имел в виду. Хранятся, конечно, данные, только из-за отсутствия в ключе информации о транзакции невозможно определить видимость ключа без определения видимости записи. Целесообразность введения в ключ номера транзакции обсуждали, но насколько я помню, признали нецелесообразным - оверхед увеличения размера ключа больше чем польза от трюков "считал индекс, данные можно не читать". Например, в индексе не хранится сотня одинаковых ключей А - хранится 1 ключ А и отсортированная цепочка номеров записей, имеющих такой ключ. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.03.2011, 10:43 |
|
||
|
Способы реализации индексов
|
|||
|---|---|---|---|
|
#18+
On 29.03.2011 19:08, Индекс Способович wrote: > Это понятно, интересует чуть больше деталей. > Интересует обычный B-tree индекс и именно варианты его реализации в различных СУБД. > Расскажите хотя бы в первом приближении. Или киньте ссылкой на материал именно > по этой теме. Там мало что можно придумать. Обычно делают префиксное сжатие ключа (как правило все ключи на странице начинаются с какого-то одного префикса, его не хранят, хранят только различающиеся суффиксы), иногда делают сжатие ключей (но это идиотизм воообще), и 2 самых дежурных темы -- -- как и когда заполнять и расщеплять страницы -- в виде чего хранить ссылки на записи в таблице. Это уже собственно к индексам мало относится, больше к архитектуре СУБД. Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.03.2011, 11:23 |
|
||
|
Способы реализации индексов
|
|||
|---|---|---|---|
|
#18+
kdvDmitry Sibiryakov косвенно намекает на общее сходство обычных индексов ФБ с индексами по выражению, которые уж точно самих данных не содержат, хотя выражение может быть A+0, т.е. даже не меняющее значения столбца. Да я, собственно, не намекаю, а прямо об этом говорю. Данные на пути в индекс всегда проходят преобразование в ключ. И функция этого преобразования - чёрный ящик. Даже если она обратима, никто об этом не знает, поэтому весь движок построен на предположении, что это преобразование необратимо. pkarklinЯ правильно понимаю, что такие понятия как covered indexes и indexes with included columns (которые позволяют снизить издержки на IO и "экономить" буфферный кэш) в IB/FB отсутвуют как класс? Именно так. За счёт этого нет проблем с регистро- и акценто-нечувствительностью при индексном доступе. Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.03.2011, 11:40 |
|
||
|
Способы реализации индексов
|
|||
|---|---|---|---|
|
#18+
Dimitry SibiryakovИменно так. За счёт этого нет проблем с регистро- и акценто-нечувствительностью при индексном доступе. О каких проблемах идет речь? Например, регистро- и акценто-нечувствительность\нечуствительность в MS SQL может быть задана вплоть до уровня отдельного поля в таблице. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.03.2011, 12:33 |
|
||
|
Способы реализации индексов
|
|||
|---|---|---|---|
|
#18+
Индекс СпособовичDimitry SibiryakovЯ сказал это потому, что я не ограничиваю пространство хэш-функций узкими рамками функций, пригодных для криптографических целей. И так да, согласно этому определению любая функция может являться хэш-функцией пока удовлетворяет условию однозначности преобразования x в f(x). Поэтому f(x)=upper(x) или f(x)=x ничем не хуже чем f(x)=md5(x). Даже лучше, поскольку при условии x<y<z выполнение условия f(x)<f(y)<f(z) позволяет получить тот самый индекс, сохраняющий информацию о порядке. И данные из индекса не берутся не только из-за отсутствия информации об их актуальности, но и потому, что данных там, собственно, нет. Применяемая для получения индексного ключа функция в общем случае необратима, что как раз свойственно хэш-функциям. ZXY<Zxy<abc и ZXY<ZXY<ABC ) Это называется коллизии, они так же не позволяют сохранять порядок. Если не ограничивать пространство арбузов узкими рамками тыквины, а ещё и яблоки арбузами называть. Я не настаиваю, но я бы предпочел называть функции подходящие под определение хэш-функции. Но не верьте мне, я просто беру частные случаи, на самом деле вы правы. Кстати, а как в Oracle с этим дело обстоит, там данные берутся из индекса? определение хэш функции соблаговолите представить :) а то получается почти как про 7 красных линий ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.03.2011, 12:44 |
|
||
|
|
start [/forum/topic.php?fid=35&msg=37188623&tid=1552702]: |
0ms |
get settings: |
10ms |
get forum list: |
12ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
33ms |
get topic data: |
11ms |
get forum data: |
3ms |
get page messages: |
61ms |
get tp. blocked users: |
1ms |
| others: | 12ms |
| total: | 149ms |
| 0 / 0 |
