Понимание реализации SSTable

Question

Я смотрю на объяснение того, как реализованы SSTable.

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

Я не понимаю выделенную часть. Если мы знаем только смещение для данного ключа, как мы будем сканировать, пока не найдем нужный ключ? Когда мы просматриваем байты после ключа, как мы узнаем, включили ли мы новый ключ или мы смотрим на действительно большое значение?

Answer 1

Сцилла описывает одну реализацию в своих документах . (У меня нет никакой связи со Сциллой. Мне просто это пригодилось.) Они хранят длину ключа для записей индекса (не совсем то, что вы ищете) в их структуре index_entry.

struct index_file {
    struct index_entry entries[];
};

struct index_entry {
    be16 key_length;
    char key[key_length];
    varint position; // decoded into a 64-bit integer
    varint promoted_index_length; // decoded into a 32-bit integer
    byte promoted_index[promoted_index_length];
};

Если ваша реализация поддерживает ключи различной длины - как я думаю, что все внедрения SSTable коммерческого уровня - это обычно для хранения их длины. В общем, программное обеспечение, которое хранит «вещи» различной длины, использует структуру данных, которая включает в себя длину «вещи». (Сцилла, вероятно, использует итератор Java.)

Answer 2

Длина каждой записи также сохраняется, так что вы можете перебирать записи.

https://github.com/google/leveldb/blob/863f185970eff21e826e5fe1164a6215a515c23b/table/block.cc#L238

https://github.com/google/leveldb/blob/863f185970eff21e826e5fe1164a6215a515c23b/table/block.cc#L61