Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
 Организация индексного фаила для двоичного поиска  [new]
mikron
Member

Откуда: Germany / Stuttgart
Сообщений: 783
Коллеги, приветствую.

У меня возникла задача создать индексный файл для быстрого двоичного поиска.
Пусть каждая запись в индексном файле имеет фиксированный размер <long key;long position>
Файл создаётся один раз и не изменяется. Здесь проблем не возникает.
Но линейное расположение записей индекса не оптимально
в плане чтения. Возникают "метания" по файлу: всегда читаем из середины файла 16 байт потом
или из 1/4 файла (с вероятностю 0.5) или из 3/4 (так же 0.5)

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

100 / 4
010 / 2
110 / 6
001 / 1
101 / 5
011 / 3
111 / 7

а порядок запросов для двоичного поиска
(1 + 8) / 2 = 4
(1 + 3) / 2 = 2
(5 + 8) / 2 = 6
...

Вот только забыл я что делать, если количество элементов не кратное. скажем 0b100011.
Может тут кто напомнит, как это правильно делается или где почитать.
23 янв 19, 13:31    [21792055]     Ответить | Цитировать Сообщить модератору
 Re: Организация индексного фаила для двоичного поиска  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 47399
mikron
Но линейное расположение записей индекса не оптимально
в плане чтения. Возникают "метания" по файлу: всегда читаем из середины файла 16 байт потом
или из 1/4 файла (с вероятностю 0.5) или из 3/4 (так же 0.5)

Именно поэтому индексы из файла обычно целиком всасывают в ОЗУ и уже там с ними работают. Размеры индексов значительно меньше, чем у данных.
23 янв 19, 14:29    [21792180]     Ответить | Цитировать Сообщить модератору
 Re: Организация индексного фаила для двоичного поиска  [new]
Dima T
Member

Откуда:
Сообщений: 13634
Добавь постраничное разбиение, например так. Этим ты уменьшишь количество страниц читаемых с диска.
23 янв 19, 14:39    [21792204]     Ответить | Цитировать Сообщить модератору
 Re: Организация индексного фаила для двоичного поиска  [new]
mayton
Member

Откуда: loopback
Сообщений: 40523
mikron
Коллеги, приветствую.

У меня возникла задача создать индексный файл для быстрого двоичного поиска.
Пусть каждая запись в индексном файле имеет фиксированный размер <long key;long position>

Ты встал на "скользкую дорожку" разработчика СУБД. Когда тебе понадобится модификация
индекса "на ходу" - почитай про B+Tree.
23 янв 19, 14:46    [21792218]     Ответить | Цитировать Сообщить модератору
 Re: Организация индексного фаила для двоичного поиска  [new]
alex55555
Member

Откуда:
Сообщений: 2100
mikron
Вот только забыл я что делать...

Сначала проверить, влазит ли индекс в память. Если не влазит - читать про организацию хранения индексов в БД.

По быстрому - можно разбить индекс на блоки, помещающиеся в памяти. Первый блок содержит вершину дерева и в памяти присутствует всегда. Остальные содержат поддеревья со ссылками либо внутри себя, либо на дополнительные поддеревья. Разбиение имеет целью максимизировать вероятность поиска в пределах одного блока, то есть в памяти. Если вероятность не реализовалась, то скачем на следующий блок, ну и т.д. Суммарно нужно минимизировать количество чтений с диска. Плюс учитывать время чтения. То есть задача на оптимизацию.
23 янв 19, 15:05    [21792272]     Ответить | Цитировать Сообщить модератору
 Re: Организация индексного фаила для двоичного поиска  [new]
mikron
Member

Откуда: Germany / Stuttgart
Сообщений: 783
Dima T
Добавь постраничное разбиение, например так. Этим ты уменьшишь количество страниц читаемых с диска.

Этим ничего не изменится. Вопрос «почему» - факультативное задание.
23 янв 19, 16:28    [21792414]     Ответить | Цитировать Сообщить модератору
 Re: Организация индексного фаила для двоичного поиска  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 7607
mikron
Dima T
Добавь постраничное разбиение, например так. Этим ты уменьшишь количество страниц читаемых с диска.

Этим ничего не изменится. Вопрос «почему» - факультативное задание.

А Кнут считал, что изменится. Вопрос «почему» - задание на прочтение книги

https://www.ozon.ru/context/detail/id/2527036/
(увидела свет в 1973 году)

)))
23 янв 19, 16:43    [21792440]     Ответить | Цитировать Сообщить модератору
 Re: Организация индексного фаила для двоичного поиска  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 7607
по ссылке Dima T вроде банальный B-Tree index.

Перечитал начальный вопрос, у тебя было как оптимизировать раскладку (сортировку) на диске. С такой постановкой вопроса - я не сталкивался, т.ч. не знаю

Но B-tree должен привести ровно к тому же эффекту. Только, если данные не будут меняться, то нужно подумать как запихать информацию в блоки "до упора" (классическое B-Tree вроде 50% заполнение блоков). Если наталкивать данные начиная с корня, то можем получить много пустых конечных блоков, которые нужно будет сливать вместе.
23 янв 19, 16:56    [21792455]     Ответить | Цитировать Сообщить модератору
 Re: Организация индексного фаила для двоичного поиска  [new]
mayton
Member

Откуда: loopback
Сообщений: 40523
mikron
Dima T
Добавь постраничное разбиение, например так. Этим ты уменьшишь количество страниц читаемых с диска.

Этим ничего не изменится. Вопрос «почему» - факультативное задание.

Мне кажется что как человек создавший топик с вопросом - ты должен быть более деликатен.
Человек тебе фактически помогает бесплатно - а ты включил менторский тон.

Так нехорошо... Нехорошо бро.
23 янв 19, 16:56    [21792456]     Ответить | Цитировать Сообщить модератору
 Re: Организация индексного фаила для двоичного поиска  [new]
mikron
Member

Откуда: Germany / Stuttgart
Сообщений: 783
Leonid Kudryavtsev
mikron
пропущено...

Этим ничего не изменится. Вопрос «почему» - факультативное задание.

А Кнут считал, что изменится. Вопрос «почему» - задание на прочтение книги

https://www.ozon.ru/context/detail/id/2527036/
(увидела свет в 1973 году)

)))

Если ты эту книгу читал, то может процетируеш авторитетный источник?
Или может сможеш даже сам обяснить что изменится?
23 янв 19, 16:57    [21792458]     Ответить | Цитировать Сообщить модератору
 Re: Организация индексного фаила для двоичного поиска  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4489
mikron,

аналогично двоичной куче, тогда следующий "загруз" всегда будет дальше по файлу

               4 (1)  
2 (2) 6 (3)
1(4) 3(5) 5(6) 7(7)
23 янв 19, 16:57    [21792460]     Ответить | Цитировать Сообщить модератору
 Re: Организация индексного фаила для двоичного поиска  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 7607
Обращение идет по блокам
В одном блоке, за одну операцию чтения, читаем сразу N записей
Записи сгрупированы (ровно то, что ты хочешь)
Сначала обращение к корню дерева, если там данных не нашлось, то обращение к следующим блокам
К блокам, которые близко лежат к корню, чаще всего обращение, они эффективно закешированы.

Т.е. никакого "метания" по файлу нет.
23 янв 19, 17:08    [21792476]     Ответить | Цитировать Сообщить модератору
 Re: Организация индексного фаила для двоичного поиска  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4489
Leonid Kudryavtsev,

он к месту сказал, например, если он индекс в память спроецирует, то последовательный доступ более благоприятен для ОС
23 янв 19, 17:12    [21792481]     Ответить | Цитировать Сообщить модератору
 Re: Организация индексного фаила для двоичного поиска  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 7607
kealon(Ruslan),

Для "чисто RAM" - будет поифг
А для диска (или даже для Virtual RAM с учетом размера страницы памяти 4 Kb), если записи сгрупировать в блоки, ровно B-tree и получим.

IMHO
23 янв 19, 17:27    [21792515]     Ответить | Цитировать Сообщить модератору
 Re: Организация индексного фаила для двоичного поиска  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4489
Leonid Kudryavtsev,
да, структура та же, только перестройка будет дорогая
23 янв 19, 18:30    [21792579]     Ответить | Цитировать Сообщить модератору
 Re: Организация индексного фаила для двоичного поиска  [new]
mayton
Member

Откуда: loopback
Сообщений: 40523
Leonid Kudryavtsev
kealon(Ruslan),

Для "чисто RAM" - будет поифг
А для диска (или даже для Virtual RAM с учетом размера страницы памяти 4 Kb), если записи сгрупировать в блоки, ровно B-tree и получим.

IMHO

Я-бы уточнил что B+Tree совершенно естественно вытекает из красно черного дерева после группировки
"кустов" в блоки с соблюдением ордеринга ключей.
23 янв 19, 18:33    [21792582]     Ответить | Цитировать Сообщить модератору
 Re: Организация индексного фаила для двоичного поиска  [new]
mikron
Member

Откуда: Germany / Stuttgart
Сообщений: 783
для расширения кругозора
23 янв 19, 18:34    [21792583]     Ответить | Цитировать Сообщить модератору
 Re: Организация индексного фаила для двоичного поиска  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4489
mayton
Я-бы уточнил что B+Tree совершенно естественно вытекает из красно черного дерева после группировки
"кустов" в блоки с соблюдением ордеринга ключей.
а отсюда вытекает ещё одна очень важна возможность
для красно-чёрного дерева есть жадные алгоритмы вставки и удаления, т.е. индекс можно изменить за один проход от корня
23 янв 19, 18:52    [21792593]     Ответить | Цитировать Сообщить модератору
 Re: Организация индексного фаила для двоичного поиска  [new]
Dima T
Member

Откуда:
Сообщений: 13634
mikron
для расширения кругозора

Расширил? Тебе уже много раз выше сказали тоже самое
For an example, consider the following two graphs, generated by running the same code on two different Intel machines. In the left graph, the Eytzinger layout is almost as slow as a plain sorted array while the van Emde Boas and B-tree layouts are more than twice as fast. In the right graph, the Eytzinger layout and b-tree are the fastest, the sorted array is still the slowest, and the vEB layout is somewhere in betweeen (for array sizes).
23 янв 19, 19:11    [21792606]     Ответить | Цитировать Сообщить модератору
 Re: Организация индексного фаила для двоичного поиска  [new]
mikron
Member

Откуда: Germany / Stuttgart
Сообщений: 783
Dima T,

Ты не ответил ни на один вопрос.
подозреваю что и сам вопрос не понял.
Безграмотно путаешь paging и b-tree.
И даже сейчас ты понятия не имееш о какой
организации данных я спрашиваю.
И утверждаеш что с самого начала знал о
результатах исследования на которое я дал здесь ссылку.
Твоё тчеславие меня утомило.

Возьму все слова назад если ты назовёшь как называется организация данных которую я описал и как строится отображение позиции в линейном массиве на эту структуру.
23 янв 19, 21:31    [21792665]     Ответить | Цитировать Сообщить модератору
 Re: Организация индексного фаила для двоичного поиска  [new]
Dima T
Member

Откуда:
Сообщений: 13634
mikron
И утверждаеш что с самого начала знал о
результатах исследования на которое я дал здесь ссылку.

Все придумано до нас. Я давал ссылку на устройство индексов MSSQL. Там решается такая же проблема: найти в индексе нужный ключ при минимальном чтении диска.

Твоя ссылка подтвердила что обычный бинарный поиск по сортированному массиву вдвое медленнее чем b-tree, что я и процитировал. В данном случае размером страницы выбран размер кэш-линии проца, т.к. чтение в кэш из памяти идет кэш-линиями.
3. btree: An implicit B-tree packed into an array using the obvious generalization of the Eytzinger layout. The value B here is chosen so that B-1 data items fit into 64 bytes (the most common cache line width).


mikron
Твоё тчеславие меня утомило.

Извините что потратил Ваше драгоценное время. Больше не буду. Удачи.
24 янв 19, 07:51    [21792816]     Ответить | Цитировать Сообщить модератору
Все форумы / Программирование Ответить