ReSQL.ru
     
powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Организация индексного фаила для двоичного поиска
21 сообщений из 21, страница 1 из 1
Организация индексного фаила для двоичного поиска
    #39763416
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikron
Участник
Коллеги, приветствую.

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

помнится мне что можно это улучшить, если записать индексный файл не линейно а в порядке "перевернутых бит"
так например для 7 записей (1..7) получится следующий порядок.
Код: plaintext
1.
2.
3.
4.
5.
6.
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.
Может тут кто напомнит, как это правильно делается или где почитать.
...
Рейтинг: 0 / 0
23.01.2019, 13:31
| Ответить | Цитировать | Написать  
Организация индексного фаила для двоичного поиска
    #39763496
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
mikronНо линейное расположение записей индекса не оптимально
в плане чтения. Возникают "метания" по файлу: всегда читаем из середины файла 16 байт потом
или из 1/4 файла (с вероятностю 0.5) или из 3/4 (так же 0.5)
Именно поэтому индексы из файла обычно целиком всасывают в ОЗУ и уже там с ними работают. Размеры индексов значительно меньше, чем у данных.
...
Рейтинг: 0 / 0
23.01.2019, 14:29
| Ответить | Цитировать | Написать  
Организация индексного фаила для двоичного поиска
    #39763507
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Добавь постраничное разбиение, например так . Этим ты уменьшишь количество страниц читаемых с диска.
...
Рейтинг: 0 / 0
23.01.2019, 14:39
| Ответить | Цитировать | Написать  
Организация индексного фаила для двоичного поиска
    #39763518
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
mikronКоллеги, приветствую.

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

Ты встал на "скользкую дорожку" разработчика СУБД. Когда тебе понадобится модификация
индекса "на ходу" - почитай про B+Tree.
...
Рейтинг: 0 / 0
23.01.2019, 14:46
| Ответить | Цитировать | Написать  
Организация индексного фаила для двоичного поиска
    #39763549
alex55555
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
alex55555
Участник
mikronВот только забыл я что делать...
Сначала проверить, влазит ли индекс в память. Если не влазит - читать про организацию хранения индексов в БД.

По быстрому - можно разбить индекс на блоки, помещающиеся в памяти. Первый блок содержит вершину дерева и в памяти присутствует всегда. Остальные содержат поддеревья со ссылками либо внутри себя, либо на дополнительные поддеревья. Разбиение имеет целью максимизировать вероятность поиска в пределах одного блока, то есть в памяти. Если вероятность не реализовалась, то скачем на следующий блок, ну и т.д. Суммарно нужно минимизировать количество чтений с диска. Плюс учитывать время чтения. То есть задача на оптимизацию.
...
Рейтинг: 0 / 0
23.01.2019, 15:05
| Ответить | Цитировать | Написать  
Организация индексного фаила для двоичного поиска
    #39763659
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikron
Участник
Dima TДобавь постраничное разбиение, например так . Этим ты уменьшишь количество страниц читаемых с диска.
Этим ничего не изменится. Вопрос «почему» - факультативное задание.
...
Рейтинг: 0 / 0
23.01.2019, 16:28
| Ответить | Цитировать | Написать  
Организация индексного фаила для двоичного поиска
    #39763681
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
mikronDima TДобавь постраничное разбиение, например так . Этим ты уменьшишь количество страниц читаемых с диска.
Этим ничего не изменится. Вопрос «почему» - факультативное задание.
А Кнут считал, что изменится. Вопрос «почему» - задание на прочтение книги

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

)))
...
Рейтинг: 0 / 0
23.01.2019, 16:43
| Ответить | Цитировать | Написать  
Организация индексного фаила для двоичного поиска
    #39763687
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
по ссылке Dima T вроде банальный B-Tree index.

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

Но B-tree должен привести ровно к тому же эффекту. Только, если данные не будут меняться, то нужно подумать как запихать информацию в блоки "до упора" (классическое B-Tree вроде 50% заполнение блоков). Если наталкивать данные начиная с корня, то можем получить много пустых конечных блоков, которые нужно будет сливать вместе.
...
Рейтинг: 0 / 0
23.01.2019, 16:56
| Ответить | Цитировать | Написать  
Организация индексного фаила для двоичного поиска
    #39763688
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
mikronDima TДобавь постраничное разбиение, например так . Этим ты уменьшишь количество страниц читаемых с диска.
Этим ничего не изменится. Вопрос «почему» - факультативное задание.
Мне кажется что как человек создавший топик с вопросом - ты должен быть более деликатен.
Человек тебе фактически помогает бесплатно - а ты включил менторский тон.

Так нехорошо... Нехорошо бро.
...
Рейтинг: 0 / 0
23.01.2019, 16:56
| Ответить | Цитировать | Написать  
Организация индексного фаила для двоичного поиска
    #39763690
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikron
Участник
Leonid Kudryavtsevmikronпропущено...

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

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

)))
Если ты эту книгу читал, то может процетируеш авторитетный источник?
Или может сможеш даже сам обяснить что изменится?
...
Рейтинг: 0 / 0
23.01.2019, 16:57
| Ответить | Цитировать | Написать  
Организация индексного фаила для двоичного поиска
    #39763692
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
mikron,

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

Код: plaintext
1.
2.
               4 (1)  
    2 (2)             6 (3)
1(4)     3(5)     5(6)    7(7)
...
Рейтинг: 0 / 0
23.01.2019, 16:57
| Ответить | Цитировать | Написать  
Организация индексного фаила для двоичного поиска
    #39763705
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
Обращение идет по блокам
В одном блоке, за одну операцию чтения, читаем сразу N записей
Записи сгрупированы (ровно то, что ты хочешь)
Сначала обращение к корню дерева, если там данных не нашлось, то обращение к следующим блокам
К блокам, которые близко лежат к корню, чаще всего обращение, они эффективно закешированы.

Т.е. никакого "метания" по файлу нет.
...
Рейтинг: 0 / 0
23.01.2019, 17:08
| Ответить | Цитировать | Написать  
Организация индексного фаила для двоичного поиска
    #39763709
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Leonid Kudryavtsev,

он к месту сказал, например, если он индекс в память спроецирует, то последовательный доступ более благоприятен для ОС
...
Рейтинг: 0 / 0
23.01.2019, 17:12
| Ответить | Цитировать | Написать  
Организация индексного фаила для двоичного поиска
    #39763737
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
kealon(Ruslan),

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

IMHO
...
Рейтинг: 0 / 0
23.01.2019, 17:27
| Ответить | Цитировать | Написать  
Организация индексного фаила для двоичного поиска
    #39763785
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Leonid Kudryavtsev,
да, структура та же, только перестройка будет дорогая
...
Рейтинг: 0 / 0
23.01.2019, 18:30
| Ответить | Цитировать | Написать  
Организация индексного фаила для двоичного поиска
    #39763787
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Leonid Kudryavtsevkealon(Ruslan),

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

IMHO
Я-бы уточнил что B+Tree совершенно естественно вытекает из красно черного дерева после группировки
"кустов" в блоки с соблюдением ордеринга ключей.
...
Рейтинг: 0 / 0
23.01.2019, 18:33
| Ответить | Цитировать | Написать  
Организация индексного фаила для двоичного поиска
    #39763788
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikron
Участник
для расширения кругозора
...
Рейтинг: 0 / 0
23.01.2019, 18:34
| Ответить | Цитировать | Написать  
Организация индексного фаила для двоичного поиска
    #39763796
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
maytonЯ-бы уточнил что B+Tree совершенно естественно вытекает из красно черного дерева после группировки
"кустов" в блоки с соблюдением ордеринга ключей.а отсюда вытекает ещё одна очень важна возможность
для красно-чёрного дерева есть жадные алгоритмы вставки и удаления, т.е. индекс можно изменить за один проход от корня
...
Рейтинг: 0 / 0
23.01.2019, 18:52
| Ответить | Цитировать | Написать  
Организация индексного фаила для двоичного поиска
    #39763804
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
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).
...
Рейтинг: 0 / 0
23.01.2019, 19:11
| Ответить | Цитировать | Написать  
Организация индексного фаила для двоичного поиска
    #39763836
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikron
Участник
Dima T,

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

Возьму все слова назад если ты назовёшь как называется организация данных которую я описал и как строится отображение позиции в линейном массиве на эту структуру.
...
Рейтинг: 0 / 0
23.01.2019, 21:31
| Ответить | Цитировать | Написать  
Организация индексного фаила для двоичного поиска
    #39763930
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
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Твоё тчеславие меня утомило.
Извините что потратил Ваше драгоценное время. Больше не буду. Удачи.
...
Рейтинг: 0 / 0
24.01.2019, 07:51
| Ответить | Цитировать | Написать  
21 сообщений из 21, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Организация индексного фаила для двоичного поиска
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&fpage=11&tid=1340002]:
 0ms
get settings:
 9ms
get forum list:
 13ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 53ms
get topic data:
 8ms
get forum data:
 2ms
get page messages:
 58ms
get tp. blocked users:
 1ms
others: 230ms
total:  382ms
созд. / загр.: 382ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]