|
|
Пишет kouzdra (![[info]](http://lj.rossia.org/img/userinfo.gif){kind=small} kouzdra)@ 2014-02-18 16:09:00 |
 |
|
 |
|
|
|
|
|
|
 |
|
 |
Про индексы
Теперь про индексы. Придумывал я это когда-то сам, хотя не думаю, что придумал что-то особенно оригинальное - идеи лежат на поверхности. Но таки для полноты:
Индексный файл логически массив пар "ключ-индекс записи", отсортированный по возрастанию ключей.
Оттуда два наблюдения:
1) скорее всего последовательные ключи имеют общий префикс, при этом его можно в следующем ключе не хранить - достаточно хранить начало расхождения
2) для локализации ключа нам достаточно знать его до первого байта, отличающего от предыдущего. Соответственно можно не хранить "хвосты". Недостаток - возможность ложного позитива - то есть запись мы нашли, но ключ в ней не в точности тот - но это фиксится проверкой после загрузки записи.
В результате мы имеем два случая:
1) ключ содержит отличие от предыдущего в известной уже нам его части - достаточно знать позицию, где возникает отличие и один новый байт - соответственно два значения - сдвиг позиции (отрицательное число) и новый байт. Обычно два байта на ключ.
2) ключ совпадает с известной нам частью предыдущего полностью и кое что к ней добавляет - длину старой части мы и так знаем - потому храним "удлинение" (положительное целое, обычно один байт) и дельту.
Случаи различаются по знаку числа.
В реальности получается примерно 2.5 байта на ключ.
Теперь индексы записей - в принципе трехбайтовые блоки, но поскольку базы имеет смысл сортировать по популярным ключам - там весьма велика вероятность что индексы будут последовательными или близкими - то есть хранить не 3-байтовые числа, а дельты - в реальности получается в среднем тоже байта полтора, два уже много. Хотя не всегда конечно.
Итого обычно - от 4 до 6-7 байтов на ключ.
Теперь пункт номер 2:
Естественно индекс, который надо сканировать с самого начала никому ни на хрен не нужен. Потому в реальности он представлялся двухуровневым "как-бы-B-деревом", внизу блоки обычно по 2-4KB устроенные вот так именно (и там поиск линейный), сверху индекс в форме "голова первого ключа в блоке - номер блока", заодно оттуда берется и начальное значение для индексации. В принципе можно было бы верхний уровень тоже по тем же принципам устроить - но вроде как незачем, и так хорошо.
PS: Еще обдумывались ситуации совсем сортированной базы с кучей повторяющихся ключей - там если есть один и тот же ключ и серия последовательно возрастающих номеров записей можно вообще в несколько байт сотни записей укладывать - даже были опытные версии такого - но он к тому времени естественным путем уже отживало свое, так что убедился в жизнеспособности идеи и плюнул.
Теперь про индексы. Придумывал я это когда-то сам, хотя не думаю, что придумал что-то особенно оригинальное - идеи лежат на поверхности. Но таки для полноты:
Индексный файл логически массив пар "ключ-индекс записи", отсортированный по возрастанию ключей.
Оттуда два наблюдения:
1) скорее всего последовательные ключи имеют общий префикс, при этом его можно в следующем ключе не хранить - достаточно хранить начало расхождения
2) для локализации ключа нам достаточно знать его до первого байта, отличающего от предыдущего. Соответственно можно не хранить "хвосты". Недостаток - возможность ложного позитива - то есть запись мы нашли, но ключ в ней не в точности тот - но это фиксится проверкой после загрузки записи.
В результате мы имеем два случая:
1) ключ содержит отличие от предыдущего в известной уже нам его части - достаточно знать позицию, где возникает отличие и один новый байт - соответственно два значения - сдвиг позиции (отрицательное число) и новый байт. Обычно два байта на ключ.
2) ключ совпадает с известной нам частью предыдущего полностью и кое что к ней добавляет - длину старой части мы и так знаем - потому храним "удлинение" (положительное целое, обычно один байт) и дельту.
Случаи различаются по знаку числа.
В реальности получается примерно 2.5 байта на ключ.
Теперь индексы записей - в принципе трехбайтовые блоки, но поскольку базы имеет смысл сортировать по популярным ключам - там весьма велика вероятность что индексы будут последовательными или близкими - то есть хранить не 3-байтовые числа, а дельты - в реальности получается в среднем тоже байта полтора, два уже много. Хотя не всегда конечно.
Итого обычно - от 4 до 6-7 байтов на ключ.
Теперь пункт номер 2:
Естественно индекс, который надо сканировать с самого начала никому ни на хрен не нужен. Потому в реальности он представлялся двухуровневым "как-бы-B-деревом", внизу блоки обычно по 2-4KB устроенные вот так именно (и там поиск линейный), сверху индекс в форме "голова первого ключа в блоке - номер блока", заодно оттуда берется и начальное значение для индексации. В принципе можно было бы верхний уровень тоже по тем же принципам устроить - но вроде как незачем, и так хорошо.
PS: Еще обдумывались ситуации совсем сортированной базы с кучей повторяющихся ключей - там если есть один и тот же ключ и серия последовательно возрастающих номеров записей можно вообще в несколько байт сотни записей укладывать - даже были опытные версии такого - но он к тому времени естественным путем уже отживало свое, так что убедился в жизнеспособности идеи и плюнул.
