Вот, после вчерашней дискуссиии набрасал приблизительную структуру храниния информации:
Подробнее…
Первоначально осуществляется поиск в массиве структур 2BIdx, содержащий структуру из из первых двух байт имени ключа и второе значение: индекс массива каталога (Dir). На рис — это самая левая тбл. тбл.
Вообще-то таблица 2BIdx не нужна, но ее использование ускоряет выборку из массивов Dir.
Массив ключей Dir представляет собой списочную структуру и имеет прибизительно следующие поля:
— Имя ключа
— указатель (а точнее индекс) на следующий элемент списка
— указатель (как вариант индекс ) на элемент Node
— уровень вложенности.
Массив ключей Dir имеет размерность 2^16 (65536) элементов — если это допустимо языком :(. Каждый массив выделяется динамически из пула памяти. Номер элемента по всем элементам массива — сквозной и вычисляется следующим образом:
— старшие два байта — номер массива Dir,
— младшие два байта — индекс в массиве.
все ключи в массиве отсортированы, по этому и используется псевдо списочная структура (чтоб свести к минимуму malloc).
Далее из структуры Dir попадаем в структуру Node. Все Node — находятся в массиве структур по 2^16 (65536) элементов. Нумерация элементов структур сквозная, алгоритм вычисления места расположенния ноды по индексу (#Node/index) аналогична как в массиве Dir
Структура Node:
— индекс в массиве Dir (обратная ссылка)
— вложенность Level
— Next, индекс следующий ноды (брата)
— First — индекс на первый элемент вложенной структуры
— указатель на данные и длинна данных.
Извлечение данных происходит по адресу. Все данные свалены в кучу без разделителей. Зная динну и адрес первого байта данных, ьы из без труда «извлекаем» и передаем на обработку.
Если блока данных не хватает, то идет запрос на следующий блок.
попробую реализовать такую схему. Может у кого будут какие дополнительные идеи?
идеи по Масштабированию (ох, далеко мне еще до него): иметь единую структуру Dir, по моим расчетам она должна занимать около 2М в памяти, в которой указывыать адрес ноды + номер сервера (например номером может быть самый старший байт структуры).
Подробнее…
Первоначально осуществляется поиск в массиве структур 2BIdx, содержащий структуру из из первых двух байт имени ключа и второе значение: индекс массива каталога (Dir). На рис — это самая левая тбл. тбл.
Вообще-то таблица 2BIdx не нужна, но ее использование ускоряет выборку из массивов Dir.
Массив ключей Dir представляет собой списочную структуру и имеет прибизительно следующие поля:
— Имя ключа
— указатель (а точнее индекс) на следующий элемент списка
— указатель (как вариант индекс ) на элемент Node
— уровень вложенности.
Массив ключей Dir имеет размерность 2^16 (65536) элементов — если это допустимо языком :(. Каждый массив выделяется динамически из пула памяти. Номер элемента по всем элементам массива — сквозной и вычисляется следующим образом:
— старшие два байта — номер массива Dir,
— младшие два байта — индекс в массиве.
все ключи в массиве отсортированы, по этому и используется псевдо списочная структура (чтоб свести к минимуму malloc).
Далее из структуры Dir попадаем в структуру Node. Все Node — находятся в массиве структур по 2^16 (65536) элементов. Нумерация элементов структур сквозная, алгоритм вычисления места расположенния ноды по индексу (#Node/index) аналогична как в массиве Dir
Структура Node:
— индекс в массиве Dir (обратная ссылка)
— вложенность Level
— Next, индекс следующий ноды (брата)
— First — индекс на первый элемент вложенной структуры
— указатель на данные и длинна данных.
Извлечение данных происходит по адресу. Все данные свалены в кучу без разделителей. Зная динну и адрес первого байта данных, ьы из без труда «извлекаем» и передаем на обработку.
Если блока данных не хватает, то идет запрос на следующий блок.
попробую реализовать такую схему. Может у кого будут какие дополнительные идеи?
идеи по Масштабированию (ох, далеко мне еще до него): иметь единую структуру Dir, по моим расчетам она должна занимать около 2М в памяти, в которой указывыать адрес ноды + номер сервера (например номером может быть самый старший байт структуры).
