| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Java EE (J2EE) и Spring > Java, B-деревья, бинарный поиск в файле |
| Автор: zhazhah 13.6.2011, 13:07 | ||
| Здравствуйте не могу разобраться как работает индекс, к примеру как организован индекс в базах данных. Как можно обратиться к любому ключу за очень маленький промежуток времени не сканируя всё подряд. Пример есть поисковый индекс с именем indexkey:
Теоретически для меня понятен бинарный поиск, делим пополам узнаём что больше что меньше и т.д пока не найдём нужное число. а как прочитать indexkey и вытянуть к примеру петя 2,4,6 бинарным поиском может кто ни будь помочь? |
| Автор: koroplysov 14.6.2011, 13:00 |
| как в базе организовано досканально не знаю, там есть свои тонкости. почитай двух томник "Фундаментальные алгоритмы на С++" по моему так называется, там очень хорошо и подробно о подобных структурах данных и алгоритмах. |
| Автор: 123qw 17.6.2011, 13:14 |
| Обязательно у записи должен быть, выражаясь терминами БД, первичный ключ, либо уникальное поле, по которому происходит индексирование. Данные упорядочены по индексу, поэтому на основании этого можно постоить бинарное дерево (тут проблем возникнуть не должно, второй курс университета). Ну, а дальше все элементарно: берешь корень дерева, сравниваешь его с ключем требуемого элемента, если больше, то преходишь в правое поддерево, если меньше в левое, если равны, то возвращаешь данные. Алгоритм продолжать рекурсивно. Аналогично и с массивом, важное условие, массив так же должен быть отсортирован по ключу. Есть массив, ты сравниваешь самый правый, самый левый и центральный элемент с ключем искомого элемента. Если все мимо, сравниваешь центральный элемент с искомым, если он (центральный) меньше, то правую границу устанавливаешь на место центрального, если меньше, то на левую границу устанавливаешь на место центрального. Алгоритм повторяешь рекурсивно. К примеру, в твоем случае мы обнаружим требуемый элемент уже на первом шаге поиска. В качестве оптимизации можно смещать правую или левую границу не на центральный элемент, а на последующий(в случае, когда смещаем левую границу) или на предыдущий (в случае, когда смещаем правую границу) относительно центрального, т.к. центральный элемент явно не наш кандидат. |