http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=Arimionim 2026-05-19T18:58:31Z Вклад участника MediaWiki 1.30.0 http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D0%BD%D0%B4%D0%B5%D0%BA%D1%81%D0%B0%D1%86%D0%B8%D1%8F_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85._%D0%A3%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BE%D1%87%D0%B5%D0%BD%D0%BD%D1%8B%D0%B5_%D0%B8_%D1%85%D0%B5%D1%88-%D0%B8%D0%BD%D0%B4%D0%B5%D0%BA%D1%81%D1%8B&diff=81667 2021-12-20T02:15:57Z

<p>Arimionim: /* Побитное расширяемое хеширование */</p> <hr /> <div>== Индексы ==<br /> <br /> Индексы нужны для того, чтобы оптимально искать нужные записи в таблице.<br /> <br /> Всего есть два способа найти нужные данные:<br /> * Полный просмотр таблицы<br /> ** Последовательный перебор записей<br /> ** Быстро работает на маленьких таблицах, но медленно на средних и больших<br /> ** Если выбираем большую часть данных, то работает быстро. Иначе - медленно<br /> * Индекс<br /> ** Произвольный набор столбцов<br /> ** Требуется предварительная обработка таблицы как при построении, так и при обновлении<br /> ** Быстрый поиск в индексе, сразу получаем указатель на запись<br /> <br /> === Кластеризованный индекс ===<br /> <br /> [[Файл:Index_Clustered.png|мини|Кластеризованный индекс]]<br /> <br /> Если данные в таблице хранятся в порядке индекса, то такой индекс называется '''кластеризованным'''. Кластеризованный индекс позволяет увеличить скорость просмотра, однако так хранить данные возможно только если в таблице есть всего один индекс.<br /> <br /> === Структура Индекса ===<br /> <br /> [[Файл:Index_Structure.png|мини|Структура индекса]]<br /> <br /> В общем случае индексы хранят отображение из ключей на идентификаторы записей, которые ведут на записи, которые мы загружаем<br /> <br /> Есть два подхода к реализации индексов: <br /> * Хеш-таблицы<br /> * Деревья поиска<br /> <br /> == Хеш-индексы == <br /> * Предварительная обработка<br /> ** Подсчет хешей ключей. Хеш-функция задается разработчиком СУБД, что дает нам гарантии хорошего статистического распределения.<br /> ** Разбиение на корзины<br /> * Поиск в индексе<br /> ** Просмотр корзины<br /> ** Несколько ключей в корзине. Коллизии могут быть, так как индекс не всегда ключ.<br /> * Заголовок помещяется в памяти<br /> [[Файл:Index_Hash_Simple.png|мини|Простой хеш-индекс]]<br /> <br /> Однако может наступить момент, когда очередная корзина не помещается в страницу, в таком случае мы так же храним их цепочками. <br /> <br /> * Так как хеш-функция хорошая, то в цепочке только полезные данные<br /> * Если цепочка длинная, значит этому набору столбцов соответствует много строк, значит база данных так и задумывалась.<br /> <br /> При этом получаем<br /> * Линейное время поиска<br /> * В случае, если данных много, мы не можем просто увеличить число корзин и перенести данные, так как перехешировать таблицу очень долго<br /> <br /> [[Файл:Index_Hash_Sequence.png|мини|Цепочки страниц]]<br /> <br /> === Расширяемое хеширование ===<br /> <br /> * Большое количество корзин, сильно больше чем требуется<br /> * Несколько корзин на одной странице, чтобы не аллоцировать для каждой корзины страницу<br /> ** Обычно - последовательных<br /> ** Разделение корзин при переполнении страницы<br /> * Не работает при плохой хеш-функции, но у нас хорошая<br /> <br /> При переполнении страницы мы:<br /> * разделяем ее на несколько страниц<br /> * разделим страницы, которые на нее ссылались, на несколько групп<br /> * Каждой такой группе выделим по странице<br /> <br /> Стоимость - 1 чтение и запись стольких страниц, на сколько мы разделили (обычно 2)<br /> <br /> [[Файл:Index_Hash_Extendable.png|мини|Расширяемое хеширование]]<br /> <br /> === Побитное расширяемое хеширование ===<br /> <br /> *Глубина хеша $n$<br /> ** Создадим $2^n$ корзин<br /> * Для каждой страницы хранится ее локальная глубина $k$<br /> ** Это значит что она хранит $2^{n−k}$ последовательных корзин на странице<br /> ** Может быть разной для разных страниц<br /> * При переполнении происходит разделение корзин<br /> ** Страница глубины $k$ разделяется на две глубины $k+1$<br /> <br /> === Ускоряемые запросы ===<br /> <br /> *Проверка существования ключа<br /> **Проверка повторений (ключи)<br /> **''in'' - только если есть все необходимые атрибуты<br /> **''exist'' - только если есть все необходимые атрибуты<br /> **''count'' - зачастую можно посчитать по индексу count, не обращаясь к самим записям<br /> *Поиск по ключу<br /> **Естественные соединения<br /> <br /> == Упорядоченные индексы ==<br /> <br /> Традиционно реализуются на деревьях поиска<br /> <br /> * Предварительная обработка<br /> ** Ключи упорядочиваются по возрастанию - так как ключ составной, то используем лексикографисечкое возрастание<br /> * Поиск в индексе<br /> ** Поиск в упорядоченной последовательности<br /> <br /> Деревья поиска<br /> * Количество операций<br /> ** Обычно пропорционально $O$(высоты)<br /> ** Минимизировать высоту<br /> * Размер узла<br /> ** Хотим эффективно использовать страницы<br /> ** Сильно ветвящиеся деревья, так размер узла будет ~странице и высота будет минимальной<br /> <br /> === $B$ и $B+$ деревья ===<br /> <br /> * $B$ деревья степени $n$<br /> ** От $\frac{n}{2}$ до n детей<br /> ** Указатели и ключи хранятся в узлах<br /> * $B+$ деревья степени $n$<br /> ** От $\frac{n}{2}$ до $n$ детей<br /> ** Указатели хранятся в листьях<br /> <br /> * $B+$ меньше данных в узлах - сильнее ветвятся<br /> * $B+$ на одну страницу глубже<br /> <br /> Мы храним корень и несколько первых уровней в памяти для быстрого обращения, из-за этого время работы может резко возрастать, когда заканчивается закешированные уровни.<br /> <br /> === Плотные и разряженные индексы ===<br /> <br /> * Плотный индекс<br /> ** Храним ключи всех элементов<br /> * Разряженные индекс<br /> ** Храним ключи части элементов<br /> ** Обычно – один на страницу, мы можем найти данные в рамках этой страницы без загрузки новых<br /> ** Разряженный индекс бычно используется для кластеризованных индексов<br /> ** Уменьшает число уровней<br /> <br /> Так как упорядоченных индекс хранит сами данные в узлах, а не только хеш, то чем больше индексируеммые данные, тем меньше степень ветвления<br /> <br /> *Строки<br /> **Много данных в ключе – меньше степень ветвления<br /> **Можно использовать префиксы<br /> Строки опасно использовать в качестве индекса, может сильно вырости высота дерева<br /> *Суррогатные ключи<br /> **Малый размер<br /> **Выше эффективность<br /> Широкие и низкие деревья - хорошо<br /> *Изменяющиеся данные<br /> **Частое обновление индекса<br /> **Уменьшение индекса<br /> Не эффективно, для уменьшения данных нужна отдельная таска<br /> <br /> <br /> === Ускоряемые запросы ===<br /> * Проверка существования ключа<br /> * Поиск по ключу<br /> * Минимум и максимум среди значений, на которых построен ключ<br /> * Диапазон <br /> ** Загрузка<br /> ** count. count * работает быстроее, так как не нужно идти по всем данным<br /> * Если построен на строках, like по префиксу<br /> <br /> ==Литература==<br /> * ''Дейт К. Введение в системы баз данных (Приложение Г)''<br /> * ''Кнут Д. Искусство программирования. Том 3. Сортировка и поиск''<br /> * ''Silberschatz A., Korth H. F., Sudarshan S. Database System Concepts''<br /> <br /> [[Категория: Базы данных]]</div>

Arimionim http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D0%BD%D0%B4%D0%B5%D0%BA%D1%81%D0%B0%D1%86%D0%B8%D1%8F_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85._%D0%A3%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BE%D1%87%D0%B5%D0%BD%D0%BD%D1%8B%D0%B5_%D0%B8_%D1%85%D0%B5%D1%88-%D0%B8%D0%BD%D0%B4%D0%B5%D0%BA%D1%81%D1%8B&diff=81666 2021-12-20T02:15:14Z

<p>Arimionim: /* Упорядоченные индексы */</p> <hr /> <div>== Индексы ==<br /> <br /> Индексы нужны для того, чтобы оптимально искать нужные записи в таблице.<br /> <br /> Всего есть два способа найти нужные данные:<br /> * Полный просмотр таблицы<br /> ** Последовательный перебор записей<br /> ** Быстро работает на маленьких таблицах, но медленно на средних и больших<br /> ** Если выбираем большую часть данных, то работает быстро. Иначе - медленно<br /> * Индекс<br /> ** Произвольный набор столбцов<br /> ** Требуется предварительная обработка таблицы как при построении, так и при обновлении<br /> ** Быстрый поиск в индексе, сразу получаем указатель на запись<br /> <br /> === Кластеризованный индекс ===<br /> <br /> [[Файл:Index_Clustered.png|мини|Кластеризованный индекс]]<br /> <br /> Если данные в таблице хранятся в порядке индекса, то такой индекс называется '''кластеризованным'''. Кластеризованный индекс позволяет увеличить скорость просмотра, однако так хранить данные возможно только если в таблице есть всего один индекс.<br /> <br /> === Структура Индекса ===<br /> <br /> [[Файл:Index_Structure.png|мини|Структура индекса]]<br /> <br /> В общем случае индексы хранят отображение из ключей на идентификаторы записей, которые ведут на записи, которые мы загружаем<br /> <br /> Есть два подхода к реализации индексов: <br /> * Хеш-таблицы<br /> * Деревья поиска<br /> <br /> == Хеш-индексы == <br /> * Предварительная обработка<br /> ** Подсчет хешей ключей. Хеш-функция задается разработчиком СУБД, что дает нам гарантии хорошего статистического распределения.<br /> ** Разбиение на корзины<br /> * Поиск в индексе<br /> ** Просмотр корзины<br /> ** Несколько ключей в корзине. Коллизии могут быть, так как индекс не всегда ключ.<br /> * Заголовок помещяется в памяти<br /> [[Файл:Index_Hash_Simple.png|мини|Простой хеш-индекс]]<br /> <br /> Однако может наступить момент, когда очередная корзина не помещается в страницу, в таком случае мы так же храним их цепочками. <br /> <br /> * Так как хеш-функция хорошая, то в цепочке только полезные данные<br /> * Если цепочка длинная, значит этому набору столбцов соответствует много строк, значит база данных так и задумывалась.<br /> <br /> При этом получаем<br /> * Линейное время поиска<br /> * В случае, если данных много, мы не можем просто увеличить число корзин и перенести данные, так как перехешировать таблицу очень долго<br /> <br /> [[Файл:Index_Hash_Sequence.png|мини|Цепочки страниц]]<br /> <br /> === Расширяемое хеширование ===<br /> <br /> * Большое количество корзин, сильно больше чем требуется<br /> * Несколько корзин на одной странице, чтобы не аллоцировать для каждой корзины страницу<br /> ** Обычно - последовательных<br /> ** Разделение корзин при переполнении страницы<br /> * Не работает при плохой хеш-функции, но у нас хорошая<br /> <br /> При переполнении страницы мы:<br /> * разделяем ее на несколько страниц<br /> * разделим страницы, которые на нее ссылались, на несколько групп<br /> * Каждой такой группе выделим по странице<br /> <br /> Стоимость - 1 чтение и запись стольких страниц, на сколько мы разделили (обычно 2)<br /> <br /> [[Файл:Index_Hash_Extendable.png|мини|Расширяемое хеширование]]<br /> <br /> === Побитное расширяемое хеширование ===<br /> <br /> *Глубина хеша $n$<br /> ** Создадим $2^n$ корзин<br /> * Для каждой страницы хранится ее локальная глубина $k$<br /> ** Это значит что она хранит $2^{n−k} последовательных корзин на странице<br /> ** Может быть разной для разных страниц<br /> * При переполнении происходит разделение корзин<br /> ** Страница глубины $k$ разделяется на две глубины $k+1$<br /> <br /> === Ускоряемые запросы ===<br /> <br /> *Проверка существования ключа<br /> **Проверка повторений (ключи)<br /> **''in'' - только если есть все необходимые атрибуты<br /> **''exist'' - только если есть все необходимые атрибуты<br /> **''count'' - зачастую можно посчитать по индексу count, не обращаясь к самим записям<br /> *Поиск по ключу<br /> **Естественные соединения<br /> <br /> == Упорядоченные индексы ==<br /> <br /> Традиционно реализуются на деревьях поиска<br /> <br /> * Предварительная обработка<br /> ** Ключи упорядочиваются по возрастанию - так как ключ составной, то используем лексикографисечкое возрастание<br /> * Поиск в индексе<br /> ** Поиск в упорядоченной последовательности<br /> <br /> Деревья поиска<br /> * Количество операций<br /> ** Обычно пропорционально $O$(высоты)<br /> ** Минимизировать высоту<br /> * Размер узла<br /> ** Хотим эффективно использовать страницы<br /> ** Сильно ветвящиеся деревья, так размер узла будет ~странице и высота будет минимальной<br /> <br /> === $B$ и $B+$ деревья ===<br /> <br /> * $B$ деревья степени $n$<br /> ** От $\frac{n}{2}$ до n детей<br /> ** Указатели и ключи хранятся в узлах<br /> * $B+$ деревья степени $n$<br /> ** От $\frac{n}{2}$ до $n$ детей<br /> ** Указатели хранятся в листьях<br /> <br /> * $B+$ меньше данных в узлах - сильнее ветвятся<br /> * $B+$ на одну страницу глубже<br /> <br /> Мы храним корень и несколько первых уровней в памяти для быстрого обращения, из-за этого время работы может резко возрастать, когда заканчивается закешированные уровни.<br /> <br /> === Плотные и разряженные индексы ===<br /> <br /> * Плотный индекс<br /> ** Храним ключи всех элементов<br /> * Разряженные индекс<br /> ** Храним ключи части элементов<br /> ** Обычно – один на страницу, мы можем найти данные в рамках этой страницы без загрузки новых<br /> ** Разряженный индекс бычно используется для кластеризованных индексов<br /> ** Уменьшает число уровней<br /> <br /> Так как упорядоченных индекс хранит сами данные в узлах, а не только хеш, то чем больше индексируеммые данные, тем меньше степень ветвления<br /> <br /> *Строки<br /> **Много данных в ключе – меньше степень ветвления<br /> **Можно использовать префиксы<br /> Строки опасно использовать в качестве индекса, может сильно вырости высота дерева<br /> *Суррогатные ключи<br /> **Малый размер<br /> **Выше эффективность<br /> Широкие и низкие деревья - хорошо<br /> *Изменяющиеся данные<br /> **Частое обновление индекса<br /> **Уменьшение индекса<br /> Не эффективно, для уменьшения данных нужна отдельная таска<br /> <br /> <br /> === Ускоряемые запросы ===<br /> * Проверка существования ключа<br /> * Поиск по ключу<br /> * Минимум и максимум среди значений, на которых построен ключ<br /> * Диапазон <br /> ** Загрузка<br /> ** count. count * работает быстроее, так как не нужно идти по всем данным<br /> * Если построен на строках, like по префиксу<br /> <br /> ==Литература==<br /> * ''Дейт К. Введение в системы баз данных (Приложение Г)''<br /> * ''Кнут Д. Искусство программирования. Том 3. Сортировка и поиск''<br /> * ''Silberschatz A., Korth H. F., Sudarshan S. Database System Concepts''<br /> <br /> [[Категория: Базы данных]]</div>

Arimionim http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D0%BD%D0%B4%D0%B5%D0%BA%D1%81%D0%B0%D1%86%D0%B8%D1%8F_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85._%D0%A3%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BE%D1%87%D0%B5%D0%BD%D0%BD%D1%8B%D0%B5_%D0%B8_%D1%85%D0%B5%D1%88-%D0%B8%D0%BD%D0%B4%D0%B5%D0%BA%D1%81%D1%8B&diff=81665 2021-12-20T02:14:54Z

<p>Arimionim: /* B и B+ деревья */</p> <hr /> <div>== Индексы ==<br /> <br /> Индексы нужны для того, чтобы оптимально искать нужные записи в таблице.<br /> <br /> Всего есть два способа найти нужные данные:<br /> * Полный просмотр таблицы<br /> ** Последовательный перебор записей<br /> ** Быстро работает на маленьких таблицах, но медленно на средних и больших<br /> ** Если выбираем большую часть данных, то работает быстро. Иначе - медленно<br /> * Индекс<br /> ** Произвольный набор столбцов<br /> ** Требуется предварительная обработка таблицы как при построении, так и при обновлении<br /> ** Быстрый поиск в индексе, сразу получаем указатель на запись<br /> <br /> === Кластеризованный индекс ===<br /> <br /> [[Файл:Index_Clustered.png|мини|Кластеризованный индекс]]<br /> <br /> Если данные в таблице хранятся в порядке индекса, то такой индекс называется '''кластеризованным'''. Кластеризованный индекс позволяет увеличить скорость просмотра, однако так хранить данные возможно только если в таблице есть всего один индекс.<br /> <br /> === Структура Индекса ===<br /> <br /> [[Файл:Index_Structure.png|мини|Структура индекса]]<br /> <br /> В общем случае индексы хранят отображение из ключей на идентификаторы записей, которые ведут на записи, которые мы загружаем<br /> <br /> Есть два подхода к реализации индексов: <br /> * Хеш-таблицы<br /> * Деревья поиска<br /> <br /> == Хеш-индексы == <br /> * Предварительная обработка<br /> ** Подсчет хешей ключей. Хеш-функция задается разработчиком СУБД, что дает нам гарантии хорошего статистического распределения.<br /> ** Разбиение на корзины<br /> * Поиск в индексе<br /> ** Просмотр корзины<br /> ** Несколько ключей в корзине. Коллизии могут быть, так как индекс не всегда ключ.<br /> * Заголовок помещяется в памяти<br /> [[Файл:Index_Hash_Simple.png|мини|Простой хеш-индекс]]<br /> <br /> Однако может наступить момент, когда очередная корзина не помещается в страницу, в таком случае мы так же храним их цепочками. <br /> <br /> * Так как хеш-функция хорошая, то в цепочке только полезные данные<br /> * Если цепочка длинная, значит этому набору столбцов соответствует много строк, значит база данных так и задумывалась.<br /> <br /> При этом получаем<br /> * Линейное время поиска<br /> * В случае, если данных много, мы не можем просто увеличить число корзин и перенести данные, так как перехешировать таблицу очень долго<br /> <br /> [[Файл:Index_Hash_Sequence.png|мини|Цепочки страниц]]<br /> <br /> === Расширяемое хеширование ===<br /> <br /> * Большое количество корзин, сильно больше чем требуется<br /> * Несколько корзин на одной странице, чтобы не аллоцировать для каждой корзины страницу<br /> ** Обычно - последовательных<br /> ** Разделение корзин при переполнении страницы<br /> * Не работает при плохой хеш-функции, но у нас хорошая<br /> <br /> При переполнении страницы мы:<br /> * разделяем ее на несколько страниц<br /> * разделим страницы, которые на нее ссылались, на несколько групп<br /> * Каждой такой группе выделим по странице<br /> <br /> Стоимость - 1 чтение и запись стольких страниц, на сколько мы разделили (обычно 2)<br /> <br /> [[Файл:Index_Hash_Extendable.png|мини|Расширяемое хеширование]]<br /> <br /> === Побитное расширяемое хеширование ===<br /> <br /> *Глубина хеша $n$<br /> ** Создадим $2^n$ корзин<br /> * Для каждой страницы хранится ее локальная глубина $k$<br /> ** Это значит что она хранит $2^{n−k} последовательных корзин на странице<br /> ** Может быть разной для разных страниц<br /> * При переполнении происходит разделение корзин<br /> ** Страница глубины $k$ разделяется на две глубины $k+1$<br /> <br /> === Ускоряемые запросы ===<br /> <br /> *Проверка существования ключа<br /> **Проверка повторений (ключи)<br /> **''in'' - только если есть все необходимые атрибуты<br /> **''exist'' - только если есть все необходимые атрибуты<br /> **''count'' - зачастую можно посчитать по индексу count, не обращаясь к самим записям<br /> *Поиск по ключу<br /> **Естественные соединения<br /> <br /> == Упорядоченные индексы ==<br /> <br /> Традиционно реализуются на деревьях поиска<br /> <br /> * Предварительная обработка<br /> ** Ключи упорядочиваются по возрастанию - так как ключ составной, то используем лексикографисечкое возрастание<br /> * Поиск в индексе<br /> ** Поиск в упорядоченной последовательности<br /> <br /> Деревья поиска<br /> * Количество операций<br /> ** Обычно пропорционально O(высоты)<br /> ** Минимизировать высоту<br /> * Размер узла<br /> ** Хотим эффективно использовать страницы<br /> ** Сильно ветвящиеся деревья, так размер узла будет ~странице и высота будет минимальной<br /> <br /> === $B$ и $B+$ деревья ===<br /> <br /> * $B$ деревья степени $n$<br /> ** От $\frac{n}{2}$ до n детей<br /> ** Указатели и ключи хранятся в узлах<br /> * $B+$ деревья степени $n$<br /> ** От $\frac{n}{2}$ до $n$ детей<br /> ** Указатели хранятся в листьях<br /> <br /> * $B+$ меньше данных в узлах - сильнее ветвятся<br /> * $B+$ на одну страницу глубже<br /> <br /> Мы храним корень и несколько первых уровней в памяти для быстрого обращения, из-за этого время работы может резко возрастать, когда заканчивается закешированные уровни.<br /> <br /> === Плотные и разряженные индексы ===<br /> <br /> * Плотный индекс<br /> ** Храним ключи всех элементов<br /> * Разряженные индекс<br /> ** Храним ключи части элементов<br /> ** Обычно – один на страницу, мы можем найти данные в рамках этой страницы без загрузки новых<br /> ** Разряженный индекс бычно используется для кластеризованных индексов<br /> ** Уменьшает число уровней<br /> <br /> Так как упорядоченных индекс хранит сами данные в узлах, а не только хеш, то чем больше индексируеммые данные, тем меньше степень ветвления<br /> <br /> *Строки<br /> **Много данных в ключе – меньше степень ветвления<br /> **Можно использовать префиксы<br /> Строки опасно использовать в качестве индекса, может сильно вырости высота дерева<br /> *Суррогатные ключи<br /> **Малый размер<br /> **Выше эффективность<br /> Широкие и низкие деревья - хорошо<br /> *Изменяющиеся данные<br /> **Частое обновление индекса<br /> **Уменьшение индекса<br /> Не эффективно, для уменьшения данных нужна отдельная таска<br /> <br /> <br /> === Ускоряемые запросы ===<br /> * Проверка существования ключа<br /> * Поиск по ключу<br /> * Минимум и максимум среди значений, на которых построен ключ<br /> * Диапазон <br /> ** Загрузка<br /> ** count. count * работает быстроее, так как не нужно идти по всем данным<br /> * Если построен на строках, like по префиксу<br /> <br /> ==Литература==<br /> * ''Дейт К. Введение в системы баз данных (Приложение Г)''<br /> * ''Кнут Д. Искусство программирования. Том 3. Сортировка и поиск''<br /> * ''Silberschatz A., Korth H. F., Sudarshan S. Database System Concepts''<br /> <br /> [[Категория: Базы данных]]</div>

Arimionim http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D0%BD%D0%B4%D0%B5%D0%BA%D1%81%D0%B0%D1%86%D0%B8%D1%8F_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85._%D0%A3%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BE%D1%87%D0%B5%D0%BD%D0%BD%D1%8B%D0%B5_%D0%B8_%D1%85%D0%B5%D1%88-%D0%B8%D0%BD%D0%B4%D0%B5%D0%BA%D1%81%D1%8B&diff=81664 2021-12-20T02:14:10Z

<p>Arimionim: </p> <hr /> <div>== Индексы ==<br /> <br /> Индексы нужны для того, чтобы оптимально искать нужные записи в таблице.<br /> <br /> Всего есть два способа найти нужные данные:<br /> * Полный просмотр таблицы<br /> ** Последовательный перебор записей<br /> ** Быстро работает на маленьких таблицах, но медленно на средних и больших<br /> ** Если выбираем большую часть данных, то работает быстро. Иначе - медленно<br /> * Индекс<br /> ** Произвольный набор столбцов<br /> ** Требуется предварительная обработка таблицы как при построении, так и при обновлении<br /> ** Быстрый поиск в индексе, сразу получаем указатель на запись<br /> <br /> === Кластеризованный индекс ===<br /> <br /> [[Файл:Index_Clustered.png|мини|Кластеризованный индекс]]<br /> <br /> Если данные в таблице хранятся в порядке индекса, то такой индекс называется '''кластеризованным'''. Кластеризованный индекс позволяет увеличить скорость просмотра, однако так хранить данные возможно только если в таблице есть всего один индекс.<br /> <br /> === Структура Индекса ===<br /> <br /> [[Файл:Index_Structure.png|мини|Структура индекса]]<br /> <br /> В общем случае индексы хранят отображение из ключей на идентификаторы записей, которые ведут на записи, которые мы загружаем<br /> <br /> Есть два подхода к реализации индексов: <br /> * Хеш-таблицы<br /> * Деревья поиска<br /> <br /> == Хеш-индексы == <br /> * Предварительная обработка<br /> ** Подсчет хешей ключей. Хеш-функция задается разработчиком СУБД, что дает нам гарантии хорошего статистического распределения.<br /> ** Разбиение на корзины<br /> * Поиск в индексе<br /> ** Просмотр корзины<br /> ** Несколько ключей в корзине. Коллизии могут быть, так как индекс не всегда ключ.<br /> * Заголовок помещяется в памяти<br /> [[Файл:Index_Hash_Simple.png|мини|Простой хеш-индекс]]<br /> <br /> Однако может наступить момент, когда очередная корзина не помещается в страницу, в таком случае мы так же храним их цепочками. <br /> <br /> * Так как хеш-функция хорошая, то в цепочке только полезные данные<br /> * Если цепочка длинная, значит этому набору столбцов соответствует много строк, значит база данных так и задумывалась.<br /> <br /> При этом получаем<br /> * Линейное время поиска<br /> * В случае, если данных много, мы не можем просто увеличить число корзин и перенести данные, так как перехешировать таблицу очень долго<br /> <br /> [[Файл:Index_Hash_Sequence.png|мини|Цепочки страниц]]<br /> <br /> === Расширяемое хеширование ===<br /> <br /> * Большое количество корзин, сильно больше чем требуется<br /> * Несколько корзин на одной странице, чтобы не аллоцировать для каждой корзины страницу<br /> ** Обычно - последовательных<br /> ** Разделение корзин при переполнении страницы<br /> * Не работает при плохой хеш-функции, но у нас хорошая<br /> <br /> При переполнении страницы мы:<br /> * разделяем ее на несколько страниц<br /> * разделим страницы, которые на нее ссылались, на несколько групп<br /> * Каждой такой группе выделим по странице<br /> <br /> Стоимость - 1 чтение и запись стольких страниц, на сколько мы разделили (обычно 2)<br /> <br /> [[Файл:Index_Hash_Extendable.png|мини|Расширяемое хеширование]]<br /> <br /> === Побитное расширяемое хеширование ===<br /> <br /> *Глубина хеша $n$<br /> ** Создадим $2^n$ корзин<br /> * Для каждой страницы хранится ее локальная глубина $k$<br /> ** Это значит что она хранит $2^{n−k} последовательных корзин на странице<br /> ** Может быть разной для разных страниц<br /> * При переполнении происходит разделение корзин<br /> ** Страница глубины $k$ разделяется на две глубины $k+1$<br /> <br /> === Ускоряемые запросы ===<br /> <br /> *Проверка существования ключа<br /> **Проверка повторений (ключи)<br /> **''in'' - только если есть все необходимые атрибуты<br /> **''exist'' - только если есть все необходимые атрибуты<br /> **''count'' - зачастую можно посчитать по индексу count, не обращаясь к самим записям<br /> *Поиск по ключу<br /> **Естественные соединения<br /> <br /> == Упорядоченные индексы ==<br /> <br /> Традиционно реализуются на деревьях поиска<br /> <br /> * Предварительная обработка<br /> ** Ключи упорядочиваются по возрастанию - так как ключ составной, то используем лексикографисечкое возрастание<br /> * Поиск в индексе<br /> ** Поиск в упорядоченной последовательности<br /> <br /> Деревья поиска<br /> * Количество операций<br /> ** Обычно пропорционально O(высоты)<br /> ** Минимизировать высоту<br /> * Размер узла<br /> ** Хотим эффективно использовать страницы<br /> ** Сильно ветвящиеся деревья, так размер узла будет ~странице и высота будет минимальной<br /> <br /> === B и B+ деревья ===<br /> <br /> * $B$ деревья степени $n$<br /> ** От $\frac{n}{2}$ до n детей<br /> ** Указатели и ключи хранятся в узлах<br /> * $B+$ деревья степени $n$<br /> ** От $\frac{n}{2}$ до n детей<br /> ** Указатели хранятся в листьях<br /> <br /> * B+ меньше данных в узлах - сильнее ветвятся<br /> * B+ на одну страницу глубже<br /> <br /> Мы храним корень и несколько первых уровней в памяти для быстрого обращения, из-за этого время работы может резко возрастать, когда заканчивается закешированные уровни.<br /> <br /> === Плотные и разряженные индексы ===<br /> <br /> * Плотный индекс<br /> ** Храним ключи всех элементов<br /> * Разряженные индекс<br /> ** Храним ключи части элементов<br /> ** Обычно – один на страницу, мы можем найти данные в рамках этой страницы без загрузки новых<br /> ** Разряженный индекс бычно используется для кластеризованных индексов<br /> ** Уменьшает число уровней<br /> <br /> Так как упорядоченных индекс хранит сами данные в узлах, а не только хеш, то чем больше индексируеммые данные, тем меньше степень ветвления<br /> <br /> *Строки<br /> **Много данных в ключе – меньше степень ветвления<br /> **Можно использовать префиксы<br /> Строки опасно использовать в качестве индекса, может сильно вырости высота дерева<br /> *Суррогатные ключи<br /> **Малый размер<br /> **Выше эффективность<br /> Широкие и низкие деревья - хорошо<br /> *Изменяющиеся данные<br /> **Частое обновление индекса<br /> **Уменьшение индекса<br /> Не эффективно, для уменьшения данных нужна отдельная таска<br /> <br /> <br /> === Ускоряемые запросы ===<br /> * Проверка существования ключа<br /> * Поиск по ключу<br /> * Минимум и максимум среди значений, на которых построен ключ<br /> * Диапазон <br /> ** Загрузка<br /> ** count. count * работает быстроее, так как не нужно идти по всем данным<br /> * Если построен на строках, like по префиксу<br /> <br /> ==Литература==<br /> * ''Дейт К. Введение в системы баз данных (Приложение Г)''<br /> * ''Кнут Д. Искусство программирования. Том 3. Сортировка и поиск''<br /> * ''Silberschatz A., Korth H. F., Sudarshan S. Database System Concepts''<br /> <br /> [[Категория: Базы данных]]</div>

Arimionim http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D0%BD%D0%B4%D0%B5%D0%BA%D1%81%D0%B0%D1%86%D0%B8%D1%8F_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85._%D0%A3%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BE%D1%87%D0%B5%D0%BD%D0%BD%D1%8B%D0%B5_%D0%B8_%D1%85%D0%B5%D1%88-%D0%B8%D0%BD%D0%B4%D0%B5%D0%BA%D1%81%D1%8B&diff=81663 2021-12-20T02:12:31Z

<p>Arimionim: /* Ускоряемые запросы */</p> <hr /> <div>== Индексы ==<br /> <br /> Индексы нужны для того, чтобы оптимально искать нужные записи в таблице.<br /> <br /> Всего есть два способа найти нужные данные:<br /> * Полный просмотр таблицы<br /> ** Последовательный перебор записей<br /> ** Быстро работает на маленьких таблицах, но медленно на средних и больших<br /> ** Если выбираем большую часть данных, то работает быстро. Иначе - медленно<br /> * Индекс<br /> ** Произвольный набор столбцов<br /> ** Требуется предварительная обработка таблицы как при построении, так и при обновлении<br /> ** Быстрый поиск в индексе, сразу получаем указатель на запись<br /> <br /> === Кластеризованный индекс ===<br /> <br /> [[Файл:Index_Clustered.png|мини|Кластеризованный индекс]]<br /> <br /> Если данные в таблице хранятся в порядке индекса, то такой индекс называется '''кластеризованным'''. Кластеризованный индекс позволяет увеличить скорость просмотра, однако так хранить данные возможно только если в таблице есть всего один индекс.<br /> <br /> === Структура Индекса ===<br /> <br /> [[Файл:Index_Structure.png|мини|Структура индекса]]<br /> <br /> В общем случае индексы хранят отображение из ключей на идентификаторы записей, которые ведут на записи, которые мы загружаем<br /> <br /> Есть два подхода к реализации индексов: <br /> * Хеш-таблицы<br /> * Деревья поиска<br /> <br /> == Хеш-индексы == <br /> * Предварительная обработка<br /> ** Подсчет хешей ключей. Хеш-функция задается разработчиком СУБД, что дает нам гарантии хорошего статистического распределения.<br /> ** Разбиение на корзины<br /> * Поиск в индексе<br /> ** Просмотр корзины<br /> ** Несколько ключей в корзине. Коллизии могут быть, так как индекс не всегда ключ.<br /> * Заголовок помещяется в памяти<br /> [[Файл:Index_Hash_Simple.png|мини|Простой хеш-индекс]]<br /> <br /> Однако может наступить момент, когда очередная корзина не помещается в страницу, в таком случае мы так же храним их цепочками. <br /> <br /> * Так как хеш-функция хорошая, то в цепочке только полезные данные<br /> * Если цепочка длинная, значит этому набору столбцов соответствует много строк, значит база данных так и задумывалась.<br /> <br /> При этом получаем<br /> * Линейное время поиска<br /> * В случае, если данных много, мы не можем просто увеличить число корзин и перенести данные, так как перехешировать таблицу очень долго<br /> <br /> [[Файл:Index_Hash_Sequence.png|мини|Цепочки страниц]]<br /> <br /> === Расширяемое хеширование ===<br /> <br /> * Большое количество корзин, сильно больше чем требуется<br /> * Несколько корзин на одной странице, чтобы не аллоцировать для каждой корзины страницу<br /> ** Обычно - последовательных<br /> ** Разделение корзин при переполнении страницы<br /> * Не работает при плохой хеш-функции, но у нас хорошая<br /> <br /> При переполнении страницы мы:<br /> * разделяем ее на несколько страниц<br /> * разделим страницы, которые на нее ссылались, на несколько групп<br /> * Каждой такой группе выделим по странице<br /> <br /> Стоимость - 1 чтение и запись стольких страниц, на сколько мы разделили (обычно 2)<br /> <br /> [[Файл:Index_Hash_Extendable.png|мини|Расширяемое хеширование]]<br /> <br /> === Побитное расширяемое хеширование ===<br /> <br /> *Глубина хеша $n$<br /> ** Создадим $2^n$ корзин<br /> * Для каждой страницы хранится ее локальная глубина $k$<br /> ** Это значит что она хранит $2^{n−k} последовательных корзин на странице<br /> ** Может быть разной для разных страниц<br /> * При переполнении происходит разделение корзин<br /> ** Страница глубины $k$ разделяется на две глубины $k+1$<br /> <br /> === Ускоряемые запросы ===<br /> <br /> *Проверка существования ключа<br /> **Проверка повторений (ключи)<br /> **''in'' - только если есть все необходимые атрибуты<br /> **''exist'' - только если есть все необходимые атрибуты<br /> **''count'' - зачастую можно посчитать по индексу count, не обращаясь к самим записям<br /> *Поиск по ключу<br /> **Естественные соединения<br /> <br /> == Упорядоченные индексы ==<br /> <br /> Традиционно реализуются на деревьях поиска<br /> <br /> * Предварительная обработка<br /> ** Ключи упорядочиваются по возрастанию - так как ключ составной, то используем лексикографисечкое возрастание<br /> * Поиск в индексе<br /> ** Поиск в упорядоченной последовательности<br /> <br /> Деревья поиска<br /> * Количество операций<br /> ** Обычно пропорционально O(высоты)<br /> ** Минимизировать высоту<br /> * Размер узла<br /> ** Хотим эффективно использовать страницы<br /> ** Сильно ветвящиеся деревья, так размер узла будет ~странице и высота будет минимальной<br /> <br /> === B и B+ деревья ===<br /> <br /> * $B$ деревья степени $n$<br /> ** От $\frac{n}{2}$ до n детей<br /> ** Указатели и ключи хранятся в узлах<br /> * $B+$ деревья степени $n$<br /> ** От $\frac{n}{2}$ до n детей<br /> ** Указатели хранятся в листьях<br /> <br /> * B+ меньше данных в узлах - сильнее ветвятся<br /> * B+ на одну страницу глубже<br /> <br /> Мы храним корень и несколько первых уровней в памяти для быстрого обращения, из-за этого время работы может резко возрастать, когда заканчивается закешированные уровни.<br /> <br /> === Плотные и разряженные индексы ===<br /> <br /> * Плотный индекс<br /> ** Храним ключи всех элементов<br /> * Разряженные индекс<br /> ** Храним ключи части элементов<br /> ** Обычно – один на страницу, мы можем найти данные в рамках этой страницы без загрузки новых<br /> ** Разряженный индекс бычно используется для кластеризованных индексов<br /> ** Уменьшает число уровней<br /> <br /> Так как упорядоченных индекс хранит сами данные в узлах, а не только хеш, то чем больше индексируеммые данные, тем меньше степень ветвления<br /> <br /> *Строки<br /> **Много данных в ключе – меньше степень ветвления<br /> **Можно использовать префиксы<br /> Строки опасно использовать в качестве индекса, может сильно вырости высота дерева<br /> *Суррогатные ключи<br /> **Малый размер<br /> **Выше эффективность<br /> Широкие и низкие деревья - хорошо<br /> *Изменяющиеся данные<br /> **Частое обновление индекса<br /> **Уменьшение индекса<br /> Не эффективно, для уменьшения данных нужна отдельная таска<br /> <br /> <br /> === Ускоряемые запросы ===<br /> * Проверка существования ключа<br /> * Поиск по ключу<br /> * Минимум и максимум среди значений, на которых построен ключ<br /> * Диапазон <br /> ** Загрузка<br /> ** count. count * работает быстроее, так как не нужно идти по всем данным<br /> * Если построен на строках, like по префиксу</div>

Arimionim http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D0%BD%D0%B4%D0%B5%D0%BA%D1%81%D0%B0%D1%86%D0%B8%D1%8F_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85._%D0%A3%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BE%D1%87%D0%B5%D0%BD%D0%BD%D1%8B%D0%B5_%D0%B8_%D1%85%D0%B5%D1%88-%D0%B8%D0%BD%D0%B4%D0%B5%D0%BA%D1%81%D1%8B&diff=81662 2021-12-20T02:10:01Z

<p>Arimionim: </p> <hr /> <div>== Индексы ==<br /> <br /> Индексы нужны для того, чтобы оптимально искать нужные записи в таблице.<br /> <br /> Всего есть два способа найти нужные данные:<br /> * Полный просмотр таблицы<br /> ** Последовательный перебор записей<br /> ** Быстро работает на маленьких таблицах, но медленно на средних и больших<br /> ** Если выбираем большую часть данных, то работает быстро. Иначе - медленно<br /> * Индекс<br /> ** Произвольный набор столбцов<br /> ** Требуется предварительная обработка таблицы как при построении, так и при обновлении<br /> ** Быстрый поиск в индексе, сразу получаем указатель на запись<br /> <br /> === Кластеризованный индекс ===<br /> <br /> [[Файл:Index_Clustered.png|мини|Кластеризованный индекс]]<br /> <br /> Если данные в таблице хранятся в порядке индекса, то такой индекс называется '''кластеризованным'''. Кластеризованный индекс позволяет увеличить скорость просмотра, однако так хранить данные возможно только если в таблице есть всего один индекс.<br /> <br /> === Структура Индекса ===<br /> <br /> [[Файл:Index_Structure.png|мини|Структура индекса]]<br /> <br /> В общем случае индексы хранят отображение из ключей на идентификаторы записей, которые ведут на записи, которые мы загружаем<br /> <br /> Есть два подхода к реализации индексов: <br /> * Хеш-таблицы<br /> * Деревья поиска<br /> <br /> == Хеш-индексы == <br /> * Предварительная обработка<br /> ** Подсчет хешей ключей. Хеш-функция задается разработчиком СУБД, что дает нам гарантии хорошего статистического распределения.<br /> ** Разбиение на корзины<br /> * Поиск в индексе<br /> ** Просмотр корзины<br /> ** Несколько ключей в корзине. Коллизии могут быть, так как индекс не всегда ключ.<br /> * Заголовок помещяется в памяти<br /> [[Файл:Index_Hash_Simple.png|мини|Простой хеш-индекс]]<br /> <br /> Однако может наступить момент, когда очередная корзина не помещается в страницу, в таком случае мы так же храним их цепочками. <br /> <br /> * Так как хеш-функция хорошая, то в цепочке только полезные данные<br /> * Если цепочка длинная, значит этому набору столбцов соответствует много строк, значит база данных так и задумывалась.<br /> <br /> При этом получаем<br /> * Линейное время поиска<br /> * В случае, если данных много, мы не можем просто увеличить число корзин и перенести данные, так как перехешировать таблицу очень долго<br /> <br /> [[Файл:Index_Hash_Sequence.png|мини|Цепочки страниц]]<br /> <br /> === Расширяемое хеширование ===<br /> <br /> * Большое количество корзин, сильно больше чем требуется<br /> * Несколько корзин на одной странице, чтобы не аллоцировать для каждой корзины страницу<br /> ** Обычно - последовательных<br /> ** Разделение корзин при переполнении страницы<br /> * Не работает при плохой хеш-функции, но у нас хорошая<br /> <br /> При переполнении страницы мы:<br /> * разделяем ее на несколько страниц<br /> * разделим страницы, которые на нее ссылались, на несколько групп<br /> * Каждой такой группе выделим по странице<br /> <br /> Стоимость - 1 чтение и запись стольких страниц, на сколько мы разделили (обычно 2)<br /> <br /> [[Файл:Index_Hash_Extendable.png|мини|Расширяемое хеширование]]<br /> <br /> === Побитное расширяемое хеширование ===<br /> <br /> *Глубина хеша $n$<br /> ** Создадим $2^n$ корзин<br /> * Для каждой страницы хранится ее локальная глубина $k$<br /> ** Это значит что она хранит $2^{n−k} последовательных корзин на странице<br /> ** Может быть разной для разных страниц<br /> * При переполнении происходит разделение корзин<br /> ** Страница глубины $k$ разделяется на две глубины $k+1$<br /> <br /> === Ускоряемые запросы ===<br /> <br /> *Проверка существования ключа<br /> **Проверка повторений (ключи)<br /> **''in'' - только если есть все необходимые атрибуты<br /> **''exist'' - только если есть все необходимые атрибуты<br /> **''count'' - зачастую можно посчитать по индексу count, не обращаясь к самим записям<br /> *Поиск по ключу<br /> **Естественные соединения<br /> <br /> == Упорядоченные индексы ==<br /> <br /> Традиционно реализуются на деревьях поиска<br /> <br /> * Предварительная обработка<br /> ** Ключи упорядочиваются по возрастанию - так как ключ составной, то используем лексикографисечкое возрастание<br /> * Поиск в индексе<br /> ** Поиск в упорядоченной последовательности<br /> <br /> Деревья поиска<br /> * Количество операций<br /> ** Обычно пропорционально O(высоты)<br /> ** Минимизировать высоту<br /> * Размер узла<br /> ** Хотим эффективно использовать страницы<br /> ** Сильно ветвящиеся деревья, так размер узла будет ~странице и высота будет минимальной<br /> <br /> === B и B+ деревья ===<br /> <br /> * $B$ деревья степени $n$<br /> ** От $\frac{n}{2}$ до n детей<br /> ** Указатели и ключи хранятся в узлах<br /> * $B+$ деревья степени $n$<br /> ** От $\frac{n}{2}$ до n детей<br /> ** Указатели хранятся в листьях<br /> <br /> * B+ меньше данных в узлах - сильнее ветвятся<br /> * B+ на одну страницу глубже<br /> <br /> Мы храним корень и несколько первых уровней в памяти для быстрого обращения, из-за этого время работы может резко возрастать, когда заканчивается закешированные уровни.<br /> <br /> === Плотные и разряженные индексы ===<br /> <br /> * Плотный индекс<br /> ** Храним ключи всех элементов<br /> * Разряженные индекс<br /> ** Храним ключи части элементов<br /> ** Обычно – один на страницу, мы можем найти данные в рамках этой страницы без загрузки новых<br /> ** Разряженный индекс бычно используется для кластеризованных индексов<br /> ** Уменьшает число уровней<br /> <br /> Так как упорядоченных индекс хранит сами данные в узлах, а не только хеш, то чем больше индексируеммые данные, тем меньше степень ветвления<br /> <br /> *Строки<br /> **Много данных в ключе – меньше степень ветвления<br /> **Можно использовать префиксы<br /> Строки опасно использовать в качестве индекса, может сильно вырости высота дерева<br /> *Суррогатные ключи<br /> **Малый размер<br /> **Выше эффективность<br /> Широкие и низкие деревья - хорошо<br /> *Изменяющиеся данные<br /> **Частое обновление индекса<br /> **Уменьшение индекса<br /> Не эффективно, для уменьшения данных нужна отдельная таска<br /> <br /> <br /> === Ускоряемые запросы ===<br /> * Проверка существования ключа<br /> * Поиск по ключу<br /> * Минимум и максимум<br /> * Диапазон<br /> ** Загрузка<br /> ** count<br /> * like по префиксу</div>

Arimionim http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D0%BD%D0%B4%D0%B5%D0%BA%D1%81%D0%B0%D1%86%D0%B8%D1%8F_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85._%D0%A3%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BE%D1%87%D0%B5%D0%BD%D0%BD%D1%8B%D0%B5_%D0%B8_%D1%85%D0%B5%D1%88-%D0%B8%D0%BD%D0%B4%D0%B5%D0%BA%D1%81%D1%8B&diff=81661 2021-12-20T02:08:29Z

<p>Arimionim: </p> <hr /> <div>== Индексы ==<br /> <br /> Индексы нужны для того, чтобы оптимально искать нужные записи в таблице.<br /> <br /> Всего есть два способа найти нужные данные:<br /> * Полный просмотр таблицы<br /> ** Последовательный перебор записей<br /> ** Быстро работает на маленьких таблицах, но медленно на средних и больших<br /> ** Если выбираем большую часть данных, то работает быстро. Иначе - медленно<br /> * Индекс<br /> ** Произвольный набор столбцов<br /> ** Требуется предварительная обработка таблицы как при построении, так и при обновлении<br /> ** Быстрый поиск в индексе, сразу получаем указатель на запись<br /> <br /> === Кластеризованный индекс ===<br /> <br /> [[Файл:Index_Clustered.png|мини|Кластеризованный индекс]]<br /> <br /> Если данные в таблице хранятся в порядке индекса, то такой индекс называется '''кластеризованным'''. Кластеризованный индекс позволяет увеличить скорость просмотра, однако так хранить данные возможно только если в таблице есть всего один индекс.<br /> <br /> === Структура Индекса ===<br /> <br /> [[Файл:Index_Structure.png|мини|Структура индекса]]<br /> <br /> В общем случае индексы хранят отображение из ключей на идентификаторы записей, которые ведут на записи, которые мы загружаем<br /> <br /> Есть два подхода к реализации индексов: <br /> * Хеш-таблицы<br /> * Деревья поиска<br /> <br /> == Хеш-индексы == <br /> * Предварительная обработка<br /> ** Подсчет хешей ключей. Хеш-функция задается разработчиком СУБД, что дает нам гарантии хорошего статистического распределения.<br /> ** Разбиение на корзины<br /> * Поиск в индексе<br /> ** Просмотр корзины<br /> ** Несколько ключей в корзине. Коллизии могут быть, так как индекс не всегда ключ.<br /> * Заголовок помещяется в памяти<br /> [[Файл:Index_Hash_Simple.png|мини|Простой хеш-индекс]]<br /> <br /> Однако может наступить момент, когда очередная корзина не помещается в страницу, в таком случае мы так же храним их цепочками. <br /> <br /> * Так как хеш-функция хорошая, то в цепочке только полезные данные<br /> * Если цепочка длинная, значит этому набору столбцов соответствует много строк, значит база данных так и задумывалась.<br /> <br /> При этом получаем<br /> * Линейное время поиска<br /> * В случае, если данных много, мы не можем просто увеличить число корзин и перенести данные, так как перехешировать таблицу очень долго<br /> <br /> [[Файл:Index_Hash_Sequence.png|мини|Цепочки страниц]]<br /> <br /> === Расширяемое хеширование ===<br /> <br /> * Большое количество корзин, сильно больше чем требуется<br /> * Несколько корзин на одной странице, чтобы не аллоцировать для каждой корзины страницу<br /> ** Обычно - последовательных<br /> ** Разделение корзин при переполнении страницы<br /> * Не работает при плохой хеш-функции, но у нас хорошая<br /> <br /> При переполнении страницы мы:<br /> * разделяем ее на несколько страниц<br /> * разделим страницы, которые на нее ссылались, на несколько групп<br /> * Каждой такой группе выделим по странице<br /> <br /> Стоимость - 1 чтение и запись стольких страниц, на сколько мы разделили (обычно 2)<br /> <br /> [[Файл:Index_Hash_Extendable.png|мини|Расширяемое хеширование]]<br /> <br /> === Побитное расширяемое хеширование ===<br /> <br /> *Глубина хеша $n$<br /> ** Создадим $2^n$ корзин<br /> * Для каждой страницы хранится ее локальная глубина $k$<br /> ** Это значит что она хранит $2^{n−k} последовательных корзин на странице<br /> ** Может быть разной для разных страниц<br /> * При переполнении происходит разделение корзин<br /> ** Страница глубины $k$ разделяется на две глубины $k+1$<br /> <br /> === Ускоряемые запросы ===<br /> <br /> *Проверка существования ключа<br /> **Проверка повторений (ключи)<br /> **''in'' - только если есть все необходимые атрибуты<br /> **''exist'' - только если есть все необходимые атрибуты<br /> **''count'' - зачастую можно посчитать по индексу count, не обращаясь к самим записям<br /> *Поиск по ключу<br /> **Естественные соединения<br /> <br /> == Упорядоченные индексы ==<br /> <br /> Традиционно реализуются на деревьях поиска<br /> <br /> * Предварительная обработка<br /> ** Ключи упорядочиваются по возрастанию - так как ключ составной, то используем лексикографисечкое возрастание<br /> * Поиск в индексе<br /> ** Поиск в упорядоченной последовательности<br /> <br /> Деревья поиска<br /> * Количество операций<br /> ** Обычно пропорционально O(высоты)<br /> ** Минимизировать высоту<br /> * Размер узла<br /> ** Хотим эффективно использовать страницы<br /> ** Сильно ветвящиеся деревья, так размер узла будет ~странице и высота будет минимальной<br /> <br /> === B и B+ деревья ===<br /> <br /> * $B$ деревья степени $n$<br /> ** От $\frac{n}{2}$ до n детей<br /> ** Указатели и ключи хранятся в узлах<br /> * $B+$ деревья степени $n$<br /> ** От $\frac{n}{2}$ до n детей<br /> ** Указатели хранятся в листьях<br /> <br /> * B+ меньше данных в узлах - сильнее ветвятся<br /> * B+ на одну страницу глубже<br /> <br /> Мы храним корень и несколько первых уровней в памяти для быстрого обращения, из-за этого время работы может резко возрастать, когда заканчивается закешированные уровни.<br /> <br /> === Плотные и разряженные индексы ===<br /> <br /> * Плотный индекс<br /> ** Храним ключи всех элементов<br /> * Разряженные индекс<br /> ** Храним ключи части элементов<br /> ** Обычно – один на страницу, мы можем найти данные в рамках этой страницы без загрузки новых<br /> ** Разряженный индекс бычно используется для кластеризованных индексов<br /> ** Уменьшает число уровней<br /> <br /> Так как упорядоченных индекс хранит сами данные в узлах, а не только хеш, то чем больше индексируеммые данные, тем меньше степень ветвления<br /> <br /> *Строки<br /> **Много данных в ключе – меньше степень ветвления<br /> **Можно использовать префиксы<br /> Строки опасно использовать в качестве индекса, может сильно вырости высота дерева<br /> *Суррогатные ключи<br /> **Малый размер<br /> **Выше эффективность<br /> Широкие и низкие деревья - хорошо<br /> *Изменяющиеся данные<br /> **Частое обновление индекса<br /> **Уменьшение индекса<br /> Не эффективно, для уменьшения данных нужна отдельная таска</div>

Arimionim http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D0%BD%D0%B4%D0%B5%D0%BA%D1%81%D0%B0%D1%86%D0%B8%D1%8F_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85._%D0%A3%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BE%D1%87%D0%B5%D0%BD%D0%BD%D1%8B%D0%B5_%D0%B8_%D1%85%D0%B5%D1%88-%D0%B8%D0%BD%D0%B4%D0%B5%D0%BA%D1%81%D1%8B&diff=81658 2021-12-20T01:59:12Z

<p>Arimionim: </p> <hr /> <div>== Индексы ==<br /> <br /> Индексы нужны для того, чтобы оптимально искать нужные записи в таблице.<br /> <br /> Всего есть два способа найти нужные данные:<br /> * Полный просмотр таблицы<br /> ** Последовательный перебор записей<br /> ** Быстро работает на маленьких таблицах, но медленно на средних и больших<br /> ** Если выбираем большую часть данных, то работает быстро. Иначе - медленно<br /> * Индекс<br /> ** Произвольный набор столбцов<br /> ** Требуется предварительная обработка таблицы как при построении, так и при обновлении<br /> ** Быстрый поиск в индексе, сразу получаем указатель на запись<br /> <br /> === Кластеризованный индекс ===<br /> <br /> [[Файл:Index_Clustered.png|мини|Кластеризованный индекс]]<br /> <br /> Если данные в таблице хранятся в порядке индекса, то такой индекс называется '''кластеризованным'''. Кластеризованный индекс позволяет увеличить скорость просмотра, однако так хранить данные возможно только если в таблице есть всего один индекс.<br /> <br /> === Структура Индекса ===<br /> <br /> [[Файл:Index_Structure.png|мини|Структура индекса]]<br /> <br /> В общем случае индексы хранят отображение из ключей на идентификаторы записей, которые ведут на записи, которые мы загружаем<br /> <br /> Есть два подхода к реализации индексов: <br /> * Хеш-таблицы<br /> * Деревья поиска<br /> <br /> == Хеш-индексы == <br /> * Предварительная обработка<br /> ** Подсчет хешей ключей. Хеш-функция задается разработчиком СУБД, что дает нам гарантии хорошего статистического распределения.<br /> ** Разбиение на корзины<br /> * Поиск в индексе<br /> ** Просмотр корзины<br /> ** Несколько ключей в корзине. Коллизии могут быть, так как индекс не всегда ключ.<br /> * Заголовок помещяется в памяти<br /> [[Файл:Index_Hash_Simple.png|мини|Простой хеш-индекс]]<br /> <br /> Однако может наступить момент, когда очередная корзина не помещается в страницу, в таком случае мы так же храним их цепочками. <br /> <br /> * Так как хеш-функция хорошая, то в цепочке только полезные данные<br /> * Если цепочка длинная, значит этому набору столбцов соответствует много строк, значит база данных так и задумывалась.<br /> <br /> При этом получаем<br /> * Линейное время поиска<br /> * В случае, если данных много, мы не можем просто увеличить число корзин и перенести данные, так как перехешировать таблицу очень долго<br /> <br /> [[Файл:Index_Hash_Sequence.png|мини|Цепочки страниц]]<br /> <br /> === Расширяемое хеширование ===<br /> <br /> * Большое количество корзин, сильно больше чем требуется<br /> * Несколько корзин на одной странице, чтобы не аллоцировать для каждой корзины страницу<br /> ** Обычно - последовательных<br /> ** Разделение корзин при переполнении страницы<br /> * Не работает при плохой хеш-функции, но у нас хорошая<br /> <br /> При переполнении страницы мы:<br /> * разделяем ее на несколько страниц<br /> * разделим страницы, которые на нее ссылались, на несколько групп<br /> * Каждой такой группе выделим по странице<br /> <br /> Стоимость - 1 чтение и запись стольких страниц, на сколько мы разделили (обычно 2)<br /> <br /> [[Файл:Index_Hash_Extendable.png|мини|Расширяемое хеширование]]<br /> <br /> === Побитное расширяемое хеширование ===<br /> <br /> *Глубина хеша $n$<br /> ** Создадим $2^n$ корзин<br /> * Для каждой страницы хранится ее локальная глубина $k$<br /> ** Это значит что она хранит $2^{n−k} последовательных корзин на странице<br /> ** Может быть разной для разных страниц<br /> * При переполнении происходит разделение корзин<br /> ** Страница глубины $k$ разделяется на две глубины $k+1$<br /> <br /> === Ускоряемые запросы ===<br /> <br /> *Проверка существования ключа<br /> **Проверка повторений (ключи)<br /> **''in'' - только если есть все необходимые атрибуты<br /> **''exist'' - только если есть все необходимые атрибуты<br /> **''count'' - зачастую можно посчитать по индексу count, не обращаясь к самим записям<br /> *Поиск по ключу<br /> **Естественные соединения<br /> <br /> == Упорядоченные индексы ==<br /> <br /> Традиционно реализуются на деревьях поиска<br /> <br /> * Предварительная обработка<br /> ** Ключи упорядочиваются по возрастанию - так как ключ составной, то используем лексикографисечкое возрастание<br /> * Поиск в индексе<br /> ** Поиск в упорядоченной последовательности<br /> <br /> Деревья поиска<br /> * Количество операций<br /> ** Обычно пропорционально O(высоты)<br /> ** Минимизировать высоту<br /> * Размер узла<br /> ** Хотим эффективно использовать страницы<br /> ** Сильно ветвящиеся деревья, так размер узла будет ~странице и высота будет минимальной<br /> <br /> === B и B+ деревья ===<br /> <br /> * $B$ деревья степени $n$<br /> ** От $\frac{n}{2}$ до n детей<br /> ** Указатели и ключи хранятся в узлах<br /> * $B+$ деревья степени $n$<br /> ** От $\frac{n}{2}$ до n детей<br /> ** Указатели хранятся в листьях<br /> <br /> * B+ меньше данных в узлах - сильнее ветвятся<br /> * B+ на одну страницу глубже<br /> <br /> Мы храним корень и несколько первых уровней в памяти для быстрого обращения</div>

Arimionim http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D0%BD%D0%B4%D0%B5%D0%BA%D1%81%D0%B0%D1%86%D0%B8%D1%8F_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85._%D0%A3%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BE%D1%87%D0%B5%D0%BD%D0%BD%D1%8B%D0%B5_%D0%B8_%D1%85%D0%B5%D1%88-%D0%B8%D0%BD%D0%B4%D0%B5%D0%BA%D1%81%D1%8B&diff=81654 2021-12-20T01:49:29Z

<p>Arimionim: </p> <hr /> <div>== Индексы ==<br /> <br /> Индексы нужны для того, чтобы оптимально искать нужные записи в таблице.<br /> <br /> Всего есть два способа найти нужные данные:<br /> * Полный просмотр таблицы<br /> ** Последовательный перебор записей<br /> ** Быстро работает на маленьких таблицах, но медленно на средних и больших<br /> ** Если выбираем большую часть данных, то работает быстро. Иначе - медленно<br /> * Индекс<br /> ** Произвольный набор столбцов<br /> ** Требуется предварительная обработка таблицы как при построении, так и при обновлении<br /> ** Быстрый поиск в индексе, сразу получаем указатель на запись<br /> <br /> === Кластеризованный индекс ===<br /> <br /> [[Файл:Index_Clustered.png|мини|Кластеризованный индекс]]<br /> <br /> Если данные в таблице хранятся в порядке индекса, то такой индекс называется '''кластеризованным'''. Кластеризованный индекс позволяет увеличить скорость просмотра, однако так хранить данные возможно только если в таблице есть всего один индекс.<br /> <br /> === Структура Индекса ===<br /> <br /> [[Файл:Index_Structure.png|мини|Структура индекса]]<br /> <br /> В общем случае индексы хранят отображение из ключей на идентификаторы записей, которые ведут на записи, которые мы загружаем<br /> <br /> Есть два подхода к реализации индексов: <br /> * Хеш-таблицы<br /> * Деревья поиска<br /> <br /> == Хеш-индексы == <br /> * Предварительная обработка<br /> ** Подсчет хешей ключей. Хеш-функция задается разработчиком СУБД, что дает нам гарантии хорошего статистического распределения.<br /> ** Разбиение на корзины<br /> * Поиск в индексе<br /> ** Просмотр корзины<br /> ** Несколько ключей в корзине. Коллизии могут быть, так как индекс не всегда ключ.<br /> * Заголовок помещяется в памяти<br /> [[Файл:Index_Hash_Simple.png|мини|Простой хеш-индекс]]<br /> <br /> Однако может наступить момент, когда очередная корзина не помещается в страницу, в таком случае мы так же храним их цепочками. <br /> <br /> * Так как хеш-функция хорошая, то в цепочке только полезные данные<br /> * Если цепочка длинная, значит этому набору столбцов соответствует много строк, значит база данных так и задумывалась.<br /> <br /> При этом получаем<br /> * Линейное время поиска<br /> * В случае, если данных много, мы не можем просто увеличить число корзин и перенести данные, так как перехешировать таблицу очень долго<br /> <br /> [[Файл:Index_Hash_Sequence.png|мини|Цепочки страниц]]<br /> <br /> === Расширяемое хеширование ===<br /> <br /> * Большое количество корзин, сильно больше чем требуется<br /> * Несколько корзин на одной странице, чтобы не аллоцировать для каждой корзины страницу<br /> ** Обычно - последовательных<br /> ** Разделение корзин при переполнении страницы<br /> * Не работает при плохой хеш-функции, но у нас хорошая<br /> <br /> При переполнении страницы мы:<br /> * разделяем ее на несколько страниц<br /> * разделим страницы, которые на нее ссылались, на несколько групп<br /> * Каждой такой группе выделим по странице<br /> <br /> Стоимость - 1 чтение и запись стольких страниц, на сколько мы разделили (обычно 2)<br /> <br /> [[Файл:Index_Hash_Extendable.png|мини|Расширяемое хеширование]]<br /> <br /> === Побитное расширяемое хеширование ===<br /> <br /> *Глубина хеша $n$<br /> ** Создадим $2^n$ корзин<br /> * Для каждой страницы хранится ее локальная глубина $k$<br /> ** Это значит что она хранит $2^{n−k} последовательных корзин на странице<br /> ** Может быть разной для разных страниц<br /> * При переполнении происходит разделение корзин<br /> ** Страница глубины $k$ разделяется на две глубины $k+1$<br /> <br /> === Ускоряемые запросы ===<br /> <br /> *Проверка существования ключа<br /> **Проверка повторений (ключи)<br /> **''in'' - только если есть все необходимые атрибуты<br /> **''exist'' - только если есть все необходимые атрибуты<br /> **''count'' - зачастую можно посчитать по индексу count, не обращаясь к самим записям<br /> *Поиск по ключу<br /> **Естественные соединения</div>

Arimionim http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D0%BD%D0%B4%D0%B5%D0%BA%D1%81%D0%B0%D1%86%D0%B8%D1%8F_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85._%D0%A3%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BE%D1%87%D0%B5%D0%BD%D0%BD%D1%8B%D0%B5_%D0%B8_%D1%85%D0%B5%D1%88-%D0%B8%D0%BD%D0%B4%D0%B5%D0%BA%D1%81%D1%8B&diff=81652 2021-12-20T01:46:22Z

<p>Arimionim: </p> <hr /> <div>== Индексы ==<br /> <br /> Индексы нужны для того, чтобы оптимально искать нужные записи в таблице.<br /> <br /> Всего есть два способа найти нужные данные:<br /> * Полный просмотр таблицы<br /> ** Последовательный перебор записей<br /> ** Быстро работает на маленьких таблицах, но медленно на средних и больших<br /> ** Если выбираем большую часть данных, то работает быстро. Иначе - медленно<br /> * Индекс<br /> ** Произвольный набор столбцов<br /> ** Требуется предварительная обработка таблицы как при построении, так и при обновлении<br /> ** Быстрый поиск в индексе, сразу получаем указатель на запись<br /> <br /> === Кластеризованный индекс ===<br /> <br /> [[Файл:Index_Clustered.png|мини|Кластеризованный индекс]]<br /> <br /> Если данные в таблице хранятся в порядке индекса, то такой индекс называется '''кластеризованным'''. Кластеризованный индекс позволяет увеличить скорость просмотра, однако так хранить данные возможно только если в таблице есть всего один индекс.<br /> <br /> === Структура Индекса ===<br /> <br /> [[Файл:Index_Structure.png|мини|Структура индекса]]<br /> <br /> В общем случае индексы хранят отображение из ключей на идентификаторы записей, которые ведут на записи, которые мы загружаем<br /> <br /> Есть два подхода к реализации индексов: <br /> * Хеш-таблицы<br /> * Деревья поиска<br /> <br /> == Хеш-индексы == <br /> * Предварительная обработка<br /> ** Подсчет хешей ключей. Хеш-функция задается разработчиком СУБД, что дает нам гарантии хорошего статистического распределения.<br /> ** Разбиение на корзины<br /> * Поиск в индексе<br /> ** Просмотр корзины<br /> ** Несколько ключей в корзине. Коллизии могут быть, так как индекс не всегда ключ.<br /> * Заголовок помещяется в памяти<br /> [[Файл:Index_Hash_Simple.png|мини|Простой хеш-индекс]]<br /> <br /> Однако может наступить момент, когда очередная корзина не помещается в страницу, в таком случае мы так же храним их цепочками. <br /> <br /> * Так как хеш-функция хорошая, то в цепочке только полезные данные<br /> * Если цепочка длинная, значит этому набору столбцов соответствует много строк, значит база данных так и задумывалась.<br /> <br /> При этом получаем<br /> * Линейное время поиска<br /> * В случае, если данных много, мы не можем просто увеличить число корзин и перенести данные, так как перехешировать таблицу очень долго<br /> <br /> [[Файл:Index_Hash_Sequence.png|мини|Цепочки страниц]]<br /> <br /> === Расширяемое хеширование ===<br /> <br /> * Большое количество корзин, сильно больше чем требуется<br /> * Несколько корзин на одной странице, чтобы не аллоцировать для каждой корзины страницу<br /> ** Обычно - последовательных<br /> ** Разделение корзин при переполнении страницы<br /> * Не работает при плохой хеш-функции, но у нас хорошая<br /> <br /> При переполнении страницы мы:<br /> * разделяем ее на несколько страниц<br /> * разделим страницы, которые на нее ссылались, на несколько групп<br /> * Каждой такой группе выделим по странице<br /> <br /> Стоимость - 1 чтение и запись стольких страниц, на сколько мы разделили (обычно 2)<br /> <br /> [[Файл:Index_Hash_Extendable.png|мини|Расширяемое хеширование]]<br /> <br /> === Побитное расширяемое хеширование ===<br /> <br /> *Глубина хеша $n$<br /> ** Создадим $2^n$ корзин<br /> * Для каждой страницы хранится ее локальная глубина $k$<br /> ** Это значит что она хранит $2^{n−k} последовательных корзин на странице<br /> ** Может быть разной для разных страниц<br /> * При переполнении происходит разделение корзин<br /> ** Страница глубины $k$ разделяется на две глубины $k+1$<br /> <br /> === Ускоряемые запросы ===<br /> <br /> *Проверка существования ключа<br /> **Проверка повторений (ключи)<br /> **''in''<br /> **''exist''<br /> **''count''<br /> *Поиск по ключу<br /> **Естественные соединения</div>

Arimionim http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D0%BD%D0%B4%D0%B5%D0%BA%D1%81%D0%B0%D1%86%D0%B8%D1%8F_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85._%D0%A3%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BE%D1%87%D0%B5%D0%BD%D0%BD%D1%8B%D0%B5_%D0%B8_%D1%85%D0%B5%D1%88-%D0%B8%D0%BD%D0%B4%D0%B5%D0%BA%D1%81%D1%8B&diff=81650 2021-12-20T01:43:11Z

<p>Arimionim: </p> <hr /> <div>== Индексы ==<br /> <br /> Индексы нужны для того, чтобы оптимально искать нужные записи в таблице.<br /> <br /> Всего есть два способа найти нужные данные:<br /> * Полный просмотр таблицы<br /> ** Последовательный перебор записей<br /> ** Быстро работает на маленьких таблицах, но медленно на средних и больших<br /> ** Если выбираем большую часть данных, то работает быстро. Иначе - медленно<br /> * Индекс<br /> ** Произвольный набор столбцов<br /> ** Требуется предварительная обработка таблицы как при построении, так и при обновлении<br /> ** Быстрый поиск в индексе, сразу получаем указатель на запись<br /> <br /> === Кластеризованный индекс ===<br /> <br /> [[Файл:Index_Clustered.png|мини|Кластеризованный индекс]]<br /> <br /> Если данные в таблице хранятся в порядке индекса, то такой индекс называется '''кластеризованным'''. Кластеризованный индекс позволяет увеличить скорость просмотра, однако так хранить данные возможно только если в таблице есть всего один индекс.<br /> <br /> === Структура Индекса ===<br /> <br /> [[Файл:Index_Structure.png|мини|Структура индекса]]<br /> <br /> В общем случае индексы хранят отображение из ключей на идентификаторы записей, которые ведут на записи, которые мы загружаем<br /> <br /> Есть два подхода к реализации индексов: <br /> * Хеш-таблицы<br /> * Деревья поиска<br /> <br /> == Хеш-индексы == <br /> * Предварительная обработка<br /> ** Подсчет хешей ключей. Хеш-функция задается разработчиком СУБД, что дает нам гарантии хорошего статистического распределения.<br /> ** Разбиение на корзины<br /> * Поиск в индексе<br /> ** Просмотр корзины<br /> ** Несколько ключей в корзине. Коллизии могут быть, так как индекс не всегда ключ.<br /> * Заголовок помещяется в памяти<br /> [[Файл:Index_Hash_Simple.png|мини|Простой хеш-индекс]]<br /> <br /> Однако может наступить момент, когда очередная корзина не помещается в страницу, в таком случае мы так же храним их цепочками. <br /> <br /> * Так как хеш-функция хорошая, то в цепочке только полезные данные<br /> * Если цепочка длинная, значит этому набору столбцов соответствует много строк, значит база данных так и задумывалась.<br /> <br /> При этом получаем<br /> * Линейное время поиска<br /> * В случае, если данных много, мы не можем просто увеличить число корзин и перенести данные, так как перехешировать таблицу очень долго<br /> <br /> [[Файл:Index_Hash_Sequence.png|мини|Цепочки страниц]]<br /> <br /> === Расширяемое хеширование ===<br /> <br /> * Большое количество корзин, сильно больше чем требуется<br /> * Несколько корзин на одной странице, чтобы не аллоцировать для каждой корзины страницу<br /> ** Обычно - последовательных<br /> ** Разделение корзин при переполнении страницы<br /> * Не работает при плохой хеш-функции, но у нас хорошая<br /> <br /> При переполнении страницы мы:<br /> * разделяем ее на несколько страниц<br /> * разделим страницы, которые на нее ссылались, на несколько групп<br /> * Каждой такой группе выделим по странице<br /> <br /> Стоимость - 1 чтение и запись стольких страниц, на сколько мы разделили (обычно 2)<br /> <br /> [[Файл:Index_Hash_Extendable.png|мини|Расширяемое хеширование]]<br /> <br /> === Побитное расширяемое хеширование ===<br /> <br /> *Глубина хеша $n$<br /> ** Создадим $2^n$ корзин<br /> * Для каждой страницы хранится ее локальная глубина $k$<br /> ** Это значит что она хранит $2^{n−k} последовательных корзин на странице<br /> ** Может быть разной для разных страниц<br /> * При переполнении происходит разделение корзин<br /> ** Страница глубины $k$ разделяется на две глубины $k+1$</div>

Arimionim http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D0%BD%D0%B4%D0%B5%D0%BA%D1%81%D0%B0%D1%86%D0%B8%D1%8F_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85._%D0%A3%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BE%D1%87%D0%B5%D0%BD%D0%BD%D1%8B%D0%B5_%D0%B8_%D1%85%D0%B5%D1%88-%D0%B8%D0%BD%D0%B4%D0%B5%D0%BA%D1%81%D1%8B&diff=81649 2021-12-20T01:42:46Z

<p>Arimionim: </p> <hr /> <div>== Индексы ==<br /> <br /> Индексы нужны для того, чтобы оптимально искать нужные записи в таблице.<br /> <br /> Всего есть два способа найти нужные данные:<br /> * Полный просмотр таблицы<br /> ** Последовательный перебор записей<br /> ** Быстро работает на маленьких таблицах, но медленно на средних и больших<br /> ** Если выбираем большую часть данных, то работает быстро. Иначе - медленно<br /> * Индекс<br /> ** Произвольный набор столбцов<br /> ** Требуется предварительная обработка таблицы как при построении, так и при обновлении<br /> ** Быстрый поиск в индексе, сразу получаем указатель на запись<br /> <br /> === Кластеризованный индекс ===<br /> <br /> [[Файл:Index_Clustered.png|мини|Кластеризованный индекс]]<br /> <br /> Если данные в таблице хранятся в порядке индекса, то такой индекс называется '''кластеризованным'''. Кластеризованный индекс позволяет увеличить скорость просмотра, однако так хранить данные возможно только если в таблице есть всего один индекс.<br /> <br /> === Структура Индекса ===<br /> <br /> [[Файл:Index_Structure.png|мини|Структура индекса]]<br /> <br /> В общем случае индексы хранят отображение из ключей на идентификаторы записей, которые ведут на записи, которые мы загружаем<br /> <br /> Есть два подхода к реализации индексов: <br /> * Хеш-таблицы<br /> * Деревья поиска<br /> <br /> == Хеш-индексы == <br /> * Предварительная обработка<br /> ** Подсчет хешей ключей. Хеш-функция задается разработчиком СУБД, что дает нам гарантии хорошего статистического распределения.<br /> ** Разбиение на корзины<br /> * Поиск в индексе<br /> ** Просмотр корзины<br /> ** Несколько ключей в корзине. Коллизии могут быть, так как индекс не всегда ключ.<br /> * Заголовок помещяется в памяти<br /> [[Файл:Index_Hash_Simple.png|мини|Простой хеш-индекс]]<br /> <br /> Однако может наступить момент, когда очередная корзина не помещается в страницу, в таком случае мы так же храним их цепочками. <br /> <br /> * Так как хеш-функция хорошая, то в цепочке только полезные данные<br /> * Если цепочка длинная, значит этому набору столбцов соответствует много строк, значит база данных так и задумывалась.<br /> <br /> При этом получаем<br /> * Линейное время поиска<br /> * В случае, если данных много, мы не можем просто увеличить число корзин и перенести данные, так как перехешировать таблицу очень долго<br /> <br /> [[Файл:Index_Hash_Sequence.png|мини|Цепочки страниц]]<br /> <br /> === Расширяемое хеширование ===<br /> <br /> * Большое количество корзин, сильно больше чем требуется<br /> * Несколько корзин на одной странице, чтобы не аллоцировать для каждой корзины страницу<br /> ** Обычно - последовательных<br /> ** Разделение корзин при переполнении страницы<br /> * Не работает при плохой хеш-функции, но у нас хорошая<br /> <br /> При переполнении страницы мы:<br /> * разделяем ее на несколько страниц<br /> * разделим страницы, которые на нее ссылались, на несколько групп<br /> * Каждой такой группе выделим по странице<br /> <br /> Стоимость - 1 чтение и запись стольких страниц, на сколько мы разделили (обычно 2)<br /> <br /> [[Файл:Index_Hash_Extendable.png|мини|Расширяемое хеширование]]<br /> <br /> === Побитное расширяемое хеширование<br /> <br /> *Глубина хеша $n$<br /> ** Создадим $2^n$ корзин<br /> * Для каждой страницы хранится ее локальная глубина $k$<br /> ** Это значит что она хранит $2^{n−k} последовательных корзин на странице<br /> ** Может быть разной для разных страниц<br /> * При переполнении происходит разделение корзин<br /> ** Страница глубины $k$ разделяется на две глубины $k+1$</div>

Arimionim http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D0%BD%D0%B4%D0%B5%D0%BA%D1%81%D0%B0%D1%86%D0%B8%D1%8F_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85._%D0%A3%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BE%D1%87%D0%B5%D0%BD%D0%BD%D1%8B%D0%B5_%D0%B8_%D1%85%D0%B5%D1%88-%D0%B8%D0%BD%D0%B4%D0%B5%D0%BA%D1%81%D1%8B&diff=81644 2021-12-20T01:31:40Z

<p>Arimionim: </p> <hr /> <div>== Индексы ==<br /> <br /> Индексы нужны для того, чтобы оптимально искать нужные записи в таблице.<br /> <br /> Всего есть два способа найти нужные данные:<br /> * Полный просмотр таблицы<br /> ** Последовательный перебор записей<br /> ** Быстро работает на маленьких таблицах, но медленно на средних и больших<br /> ** Если выбираем большую часть данных, то работает быстро. Иначе - медленно<br /> * Индекс<br /> ** Произвольный набор столбцов<br /> ** Требуется предварительная обработка таблицы как при построении, так и при обновлении<br /> ** Быстрый поиск в индексе, сразу получаем указатель на запись<br /> <br /> === Кластеризованный индекс ===<br /> <br /> [[Файл:Index_Clustered.png|мини|Кластеризованный индекс]]<br /> <br /> Если данные в таблице хранятся в порядке индекса, то такой индекс называется '''кластеризованным'''. Кластеризованный индекс позволяет увеличить скорость просмотра, однако так хранить данные возможно только если в таблице есть всего один индекс.<br /> <br /> === Структура Индекса ===<br /> <br /> [[Файл:Index_Structure.png|мини|Структура индекса]]<br /> <br /> В общем случае индексы хранят отображение из ключей на идентификаторы записей, которые ведут на записи, которые мы загружаем<br /> <br /> Есть два подхода к реализации индексов: <br /> * Хеш-таблицы<br /> * Деревья поиска<br /> <br /> == Хеш-индексы == <br /> * Предварительная обработка<br /> ** Подсчет хешей ключей. Хеш-функция задается разработчиком СУБД, что дает нам гарантии хорошего статистического распределения.<br /> ** Разбиение на корзины<br /> * Поиск в индексе<br /> ** Просмотр корзины<br /> ** Несколько ключей в корзине. Коллизии могут быть, так как индекс не всегда ключ.<br /> * Заголовок помещяется в памяти<br /> [[Файл:Index_Hash_Simple.jpg|мини|Простой хеш-индекс]]<br /> <br /> Однако может наступить момент, когда очередная корзина не помещается в страницу, в таком случае мы так же храним их цепочками. <br /> <br /> * Так как хеш-функция хорошая, то в цепочке только полезные данные<br /> * Если цепочка длинная, значит этому набору столбцов соответствует много строк, значит база данных так и задумывалась.<br /> <br /> При этом получаем<br /> * Линейное время поиска<br /> * В случае, если данных много, мы не можем просто увеличить число корзин и перенести данные, так как перехешировать таблицу очень долго<br /> <br /> [[Файл:Index_Hash_Sequence.png|мини|Цепочки страниц]]<br /> <br /> === Расширяемое хеширование<br /> <br /> * Большое количество корзин<br /> * Несколько корзин на одной странице<br /> ** Обычно - последовательных<br /> ** Разделение корзин при переполнении страницы<br /> * Не работает при плохой хеш-функции, но у нас хорошая<br /> <br /> [[Файл:Index_Hash_Extendable.png|мини|Расширяемое хеширование]]</div>

Arimionim http://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Index_Hash_Extendable.png&diff=81643 2021-12-20T01:30:24Z

<p>Arimionim: </p> <hr /> <div></div>

Arimionim http://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Index_Hash_Sequence.png&diff=81641 2021-12-20T01:23:06Z

<p>Arimionim: </p> <hr /> <div></div>

Arimionim http://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Index_Hash_Simple.png&diff=81640 2021-12-20T01:19:35Z

<p>Arimionim: </p> <hr /> <div></div>

Arimionim http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D0%BD%D0%B4%D0%B5%D0%BA%D1%81%D0%B0%D1%86%D0%B8%D1%8F_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85._%D0%A3%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BE%D1%87%D0%B5%D0%BD%D0%BD%D1%8B%D0%B5_%D0%B8_%D1%85%D0%B5%D1%88-%D0%B8%D0%BD%D0%B4%D0%B5%D0%BA%D1%81%D1%8B&diff=81639 2021-12-20T01:02:26Z

<p>Arimionim: </p> <hr /> <div>== Индексы ==<br /> <br /> Индексы нужны для того, чтобы оптимально искать нужные записи в таблице.<br /> <br /> Всего есть два способа найти нужные данные:<br /> * Полный просмотр таблицы<br /> ** Последовательный перебор записей<br /> ** Быстро работает на маленьких таблицах, но медленно на средних и больших<br /> ** Если выбираем большую часть данных, то работает быстро. Иначе - медленно<br /> * Индекс<br /> ** Произвольный набор столбцов<br /> ** Требуется предварительная обработка таблицы как при построении, так и при обновлении<br /> ** Быстрый поиск в индексе, сразу получаем указатель на запись<br /> <br /> === Кластеризованный индекс ===<br /> <br /> [[Файл:Index_Clustered.png|мини|Кластеризованный индекс]]<br /> <br /> Если данные в таблице хранятся в порядке индекса, то такой индекс называется '''кластеризованным'''. Кластеризованный индекс позволяет увеличить скорость просмотра, однако так хранить данные возможно только если в таблице есть всего один индекс.<br /> <br /> === Структура Индекса ===<br /> <br /> [[Файл:Index_Structure.png|мини|Структура индекса]]<br /> <br /> В общем случае индексы хранят отображение из ключей на идентификаторы записей, которые ведут на записи, которые мы загружаем<br /> <br /> Есть два подхода к реализации индексов: <br /> * Хеш-таблицы<br /> * Деревья поиска<br /> <br /> == Хеш-индексы == <br /> * Предварительная обработка<br /> ** Подсчет хешей ключей. Хеш-функция задается разработчиком СУБД, что дает нам гарантии хорошего статистического распределения.<br /> ** Разбиение на корзины<br /> * Поиск в индексе<br /> ** Просмотр корзины<br /> ** Несколько ключей в корзине. Коллизии могут быть, так как индекс не всегда ключ.<br /> * Заголовок помещяется в памяти</div>

Arimionim http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D0%BD%D0%B4%D0%B5%D0%BA%D1%81%D0%B0%D1%86%D0%B8%D1%8F_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85._%D0%A3%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BE%D1%87%D0%B5%D0%BD%D0%BD%D1%8B%D0%B5_%D0%B8_%D1%85%D0%B5%D1%88-%D0%B8%D0%BD%D0%B4%D0%B5%D0%BA%D1%81%D1%8B&diff=81638 2021-12-20T00:51:43Z

<p>Arimionim: </p> <hr /> <div>== Индексы ==<br /> <br /> Индексы нужны для того, чтобы оптимально искать нужные записи в таблице.<br /> <br /> Всего есть два способа найти нужные данные:<br /> * Полный просмотр таблицы<br /> ** Последовательный перебор записей<br /> ** Быстро работает на маленьких таблицах, но медленно на средних и больших<br /> ** Если выбираем большую часть данных, то работает быстро. Иначе - медленно<br /> * Индекс<br /> ** Произвольный набор столбцов<br /> ** Требуется предварительная обработка таблицы как при построении, так и при обновлении<br /> ** Быстрый поиск в индексе, сразу получаем указатель на запись<br /> <br /> === Кластеризованный индекс ===<br /> <br /> [[Файл:Index_Clustered.png|мини|Кластеризованный индекс]]<br /> <br /> Если данные в таблице хранятся в порядке индекса, то такой индекс называется '''кластеризованным'''. Кластеризованный индекс позволяет увеличить скорость просмотра, однако так хранить данные возможно только если в таблице есть всего один индекс.<br /> <br /> === Структура Индекса ===<br /> <br /> [[Файл:Index_Structure.png|мини|Структура индекса]]<br /> <br /> В общем случае индексы хранят отображение из ключей на идентификаторы записей, которые ведут на записи, которые мы загружаем</div>

Arimionim http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D0%BD%D0%B4%D0%B5%D0%BA%D1%81%D0%B0%D1%86%D0%B8%D1%8F_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85._%D0%A3%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BE%D1%87%D0%B5%D0%BD%D0%BD%D1%8B%D0%B5_%D0%B8_%D1%85%D0%B5%D1%88-%D0%B8%D0%BD%D0%B4%D0%B5%D0%BA%D1%81%D1%8B&diff=81637 2021-12-20T00:46:51Z

<p>Arimionim: /* Кластеризованный индекс */</p> <hr /> <div>== Индексы ==<br /> <br /> Индексы нужны для того, чтобы оптимально искать нужные записи в таблице.<br /> <br /> Всего есть два способа найти нужные данные:<br /> * Полный просмотр таблицы<br /> ** Последовательный перебор записей<br /> ** Быстро работает на маленьких таблицах, но медленно на средних и больших<br /> ** Если выбираем большую часть данных, то работает быстро. Иначе - медленно<br /> * Индекс<br /> ** Произвольный набор столбцов<br /> ** Требуется предварительная обработка таблицы как при построении, так и при обновлении<br /> ** Быстрый поиск в индексе, сразу получаем указатель на запись<br /> <br /> === Кластеризованный индекс ===<br /> <br /> [[Файл:Index_Clustered.png|мини]]<br /> <br /> Если данные в таблице хранятся в порядке индекса, то такой индекс называется '''кластеризованным'''. Кластеризованный индекс позволяет увеличить скорость просмотра, однако так хранить данные возможно только если в таблице есть всего один индекс.</div>

Arimionim http://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Index_Clustered.png&diff=81636 2021-12-20T00:38:30Z

<p>Arimionim: </p> <hr /> <div></div>

Arimionim http://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Index_Structure.png&diff=81635 2021-12-20T00:37:57Z

<p>Arimionim: </p> <hr /> <div></div>

Arimionim