Индексы базы данных

Question

Мне нужно разработать «наивную» реализацию индексов базы данных для использования в распределенной среде. Я почти ничего не знаю об этом предмете, и меня немного подталкивает время.

Я хотел бы услышать некоторые мнения, примеры и алгоритмы по этому вопросу. Я хотел бы иметь представление о том, что мне нужно реализовать.

EDIT: Я имею в виду кластерные индексы

Answer 1

Есть в основном два основных типа индексов:

• кластерного (т.е. данные физически организованы, и вы вновь разбирайтесь при каждой вставке, если необходимо)

  Типичный прецедент: физическая организация обычно совпадает с порядком вставки, поэтому перераспределение служебных данных не является проблемой. Это, например, случай с последовательными UID (так называемые поля «IDENTITY» в контексте базы данных)

  Очевидным недостатком кластеризованного индексации является то, что вы можете иметь только один такой индекс для своих данных.

  Наивная реализация, если порядок вставки - это точно порядок сортировки: используйте Список.

  1. вставки O (1): вы просто добавить новые данные в списке
  2. Доступ O (1), если идентификаторы являются последовательными (т.е. индексы массива в точности совпадает с UID), O (журнал) в противном случае

• некластеризованной (т.е. вы держите указатели на данные, как в Hashtable)

  Типичные сценарии использования: кластеризация не подходит, потому что это будет побуждать к большим накладные расходы вставки.

В зависимости от ваших потребностей, вы, вероятно, в конечном итоге, используя на этих двух datastructures

Обширное хранилище информации Index связанных доступен here

Answer 2

Действительно быстро и-Easy- чтобы реализовать, действительно наивную реализацию индекса, наиболее подходящую для любого языка, который имеет собственный формат associative array, является хешем, ключи которого являются постоянными значениями для индекса, который вы индексируете, и значениями которого являются массивы идентификаторов строк для строк с этим значением ,