TreeDb. Структура данных

    Вот, после вчерашней дискуссиии набрасал приблизительную структуру храниния информации:

    Подробнее…

    Первоначально осуществляется поиск в массиве структур 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М в памяти, в которой указывыать адрес ноды + номер сервера (например номером может быть самый старший байт структуры).
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 27

      +3
      Мало запутанных рисунков! Требую больше рисунков с большим количеством линий.!
        0
        излишняя детализация — вредна
        0
        транзакции будут?
          0
          пока не планируется,
          нужны?
            0
            разумеется.
              0
              сделать бы без них, прикрутить блокировки, дело не хитрое (я так думаю, когда ближе к делу, то видно будет чего копать и куда рыть...).
              вообще-то я планирую использовать БД как гибкий справочник.
                0
                вообще-то тут дело не в блокировках а в журналировании. что будет если клиент между двумя связанными запросами на изменение упадёт? правильно, сломанная база данных.
                  0
                  имеется ввиду цикл транзакции:
                  BEGIN TRANSACTION
                  set…
                  set…
                  END TRANSACTION

                  нет, пока этого точно не планирую. Блокировку на запись прикручу обязательно.

                  Если буду делать транзакции, то уже сл. этапом, как развитие системы.
                    +1
                    создать создать пользователя
                    [тут скрипт упал]
                    поднять для только что созданного пользователя биллинг
                    [опа, пользователь есть, а биллинга нет]

                    далее каскадно падают все скрипты использующие биллинг
                      0
                      ну, на мой взгляд — эта бд в том виде, как я ее задумывал — для биллинга навряд ли пригодится. Она ограничена размером оперативки, как редис.

                      держать информацию блоками на файлах, и подгружать блоки по мере необходимости — это будет сл. этап, но тут сразу появятся тормоза. Это как sedna — быстра и удобна, пока все данные сидят в оперативки (на больших объемах обгоняет мускуль на ура), но как толькопоиск выходит за пределы блока, то наступают сильные тормоза.

                      Думаю, что возможен учет, если БД использовать как учетную систему с нарастающим итогом, т.е. в режиме счетчика кликов (без учета времени клика)

                      теперь ближе к телу:
                      мы создаем пользователя и поднимаем биллинг в пределах одной команды set (большой мультисет): если да, то целостность сохраниться. Либо команда выполниться, либо нет.

                      Один поток обслуживает одного клиента. Приняли команду, распарсили и выдали на исполнение.

                      если несколько сетов, то тут уж извините. Хотите целостность, Старайтесь вносить данные в пределах одного мультисета.
                        0
                        сделаешь тьюринг-полный мультисет? х)
                          0
                          постараюсь
                          а помочь не хочешь?
                            0
                            неее %-)
                              0
                              а чего боишься?
                              Си — знаешь?
                                0
                                угу, а ещё я знаю своего соседа… но это не значит, что я хочу с ним ебаться х)
                                  0
                                  ладно, буду ждать критики
                                  вчера почвилась первая строчка кода
                    0
                    >что будет если клиент между двумя связанными запросами на изменение упадёт?
                    перезапишет эти данные, все что до падения передалось на сервер — будет внесено.

                    транзакции снижают скорость (это доп буфер, доп перемещения данных), а у меня пока основной критерий — это скорость.
                      0
                      ну да, а целостность данных — сущий пустяк х))
                        0
                        приведи пример в контексте этой БД
                          0
                          можешь не приводить, примером выше ты правильно описал ситуацию
              –1
              а попонятнее можно?
                0
                что конкретно непонятно?
                предыстория вопроса в предыдущем посте (ссылка в самом начале поста).
                +1
                хм, а финал версия вашей db это… логотип хабра?
                  0
                  юмор оценен,
                  держи пять!
                  +1
                  Ого, при такой структуре удаление и добавление элементов будет очень медленным же. Особенно учитывая отсортированность. Изменение элемента — да, будет быстрым, но изменение кол-ва элементов приведет к пересортировке структуры.
                    0
                    Думаю, изменение и удаление не очень частые операции. Я делал упор на выборку.

                    Вставка нового элемента будет относительно быстро: встака элемента в список Dir + добавление нового элемента (вместо из пула ) Node + сами данные (вместо из пула )

                    Удаление элемента — операция специфическая, удаление элемента из 2BIdx труда не представляет. Освобождение ячейки в Dir — надо память как-то вернуть в пул. В идеале, если это был последний элемент, то без проблем. Но, идеала не бывает, по этому необходимо учитывать сегментированные куски памяти. Можно на них забить (учитывть только %%) и, например при сегментированности в 30% просто тупо восстановить данные с диска (потеря производительности на 1 транзакции). Тут конечно надо будет эксперементировать.
                    Ну и конечно же вылезает проблема сегментации в пуле Data.
                      0
                      а вот вставка элемента в существующую структуру будет помедленней. Действительно, потребуется дополнительное время на просмотра списка дочерних элементов Node, и встака в него данного элемента.

                      Сортировка, очевидно потребуется только один раз — при создании списка Node нового уровня (вставляем элемент и подэлементы).

                    Only users with full accounts can post comments. Log in, please.