Создание индекса для отсортированных данных

Question

У меня есть текстовый файл с некоторыми отсортированными данными, разделенный символом новой строки. например:

...
abc123
abc124
abd123
abd124
abd125
...

Теперь я хочу создать индекс для набора данных, который должен (по крайней мере) поддержка:

1. getStringByIndex (п): вернуть п-й элемент из отсортированный список;

2. getIndexByString (s): найти s во всех элементах, вернуть его индекс (или -1, если не найден);

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

Answer 1

Поскольку данные сортируются, вы можете находить контент очень быстро и эффективно, просто сохраняя небольшое, разреженное подмножество данных в памяти. Например, предположим, что мы решили хранить каждый N-й элемент в памяти. Для эффективной инициализации вашего API вы хотите скомпилировать этот разреженный список в отдельном файле на диске, поэтому вам не нужно передавать через 100 ГБ данных для его получения.

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

getStringByIndex(n): 
     Get floor(n/N)-th string/offset pair from list 
     Seek offset position in index 
     Read/Skip n mod N strings, then return the next one 

    getIndexByString(s): 
     Binary search over sparse list in memory 
      Locate lower and upper bound string/offset pairs 
     If a string/offset pair is in the i-th position in our sparse list, 
      then the string itself is the (N x i)-th string in our index. 
      We can use this information to compute the return value 
     If the string we want isn't in memory: 
      Seek lower-bound offset in index 
      Read strings until we: 
       a) Find a match 
       b) Reach the high-bound offset 
       c) Reach a string which is lexicographically greater than the one we are looking for 
     Else 
      Just return the index for the matching string in our sparse list 

Если строки в индексе имеют фиксированную ширину, вы можете сделать еще большую оптимизацию.

Вы должны быть осторожны относительно вашего выбора «N» для этого алгоритма, если вы его реализуете. Помните, что стоимость чтения 10 байт из позиции на диске не намного ниже стоимости чтения 10 000 байт из этой же позиции: это накладные расходы на поиск диска и получение и выключение вызова ввода-вывода, который болит больше всего.