Как я могу проиндексировать дерево в таблице SQLite?

Question

У меня есть таблица со следующими полями:

id      VARCHAR(32) PRIMARY KEY,
parent  VARCHAR(32),
name    VARCHAR(32)

parent - это внешний ключ, ссылающийся на ту же таблицу. Эта структура генерирует дерево. Это дерево должно копировать дерево файловой системы. Проблема в том, что поиск идентификатора из пути - это slooow. Поэтому я хочу построить индекс. Каков наилучший способ сделать это?

Пример данных:

   id          parent        name
--------    -----------    ----------
   1            NULL          root
   2             1            foo
   3             1            bar
   4             3            baz
   5             4            aii

будет индексировать к:

   id          parent        name
--------    -----------    ----------
   1            NULL          root
   2             1            root/foo
   3             1            root/bar
   4             3            root/bar/baz
   5             4            root/bar/baz/aii

В настоящее время я думаю об использовании временной таблицы и кода, выполняющего вручную серию операций вставки из для создания индекса. (Причина, по которой я делаю это временным, заключается в том, что если к этой базе данных обращаются из системы Windows, путь требует обратной косой черты, тогда как от * nix это требует прямой косой черты). Есть ли альтернатива этому?

Answer 1

Итак, у вас есть функция, которая делает что-то вроде этого (псевдокод):

int getId(char **path) {
    int id = 0;
    int i;
    char query[1000];

    for (i = 0; path[i] != NULL; i++) {
        sprintf(query, "select id from table where parent = %d and name = '%s'", id, name);
        id = QuerySimple(query);
        if (id < 0)
           break;
    }
    return id;
}

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

(временная) таблица может использоваться, как вы сказали, обратите внимание, что вы можете изменить разделитель пути в своей программе, избегая необходимости разных таблиц для Windows и Unix. Вам также необходимо поддерживать дополнительную таблицу в синхронизации с мастером. если обновления / удаления / вставки редки, вместо таблицы вы можете просто сохранить в памяти кеш уже просмотренных данных и очистить кеш при обновлении (вы также можете сделать частичное удаление в кеше, если хотите ). В этом случае вы также можете прочитать больше данных (например, если родитель прочитал все дочерние элементы), чтобы быстрее заполнить кэш. В крайнем случае, вы можете прочитать всю таблицу в памяти и работать там! это зависит от того, сколько у вас данных, ваши типовые шаблоны доступа (сколько операций чтения, сколько операций записи) и среды развертывания (у вас есть резервная память?).