Как бы вы представили коллекцию хэш-таблиц в схеме базы данных?

https://stackoverflow.com/questions/449202

19-08-2019
|

Вопрос

Если вы пытались создать объект домена в схеме базы данных, и в вашем коде указанный объект домена имеет элемент хэш-таблицы / списка, например:

public class SpaceQuadrant : PersistentObject
{

    public SpaceQuadrant()
    {
    }

    public virtual Dictionary<SpaceCoordinate, SpaceObject> Space
    {
        get;
        set;
    }
}

Словарь - это просто хеш-таблица / список, сопоставляющий ключи объектов с ключами значений, я придумал несколько способов сделать это, создавая различные таблицы соединений или методы загрузки, но все они в некотором роде отстой с точки зрения получения того O (1) времени доступа, которое вы получаете в хеш-таблице.

Как бы вы представили SpaceQuadrant, SpaceCoordinate и космический объект в схеме базы данных?Простое описание кода схемы было бы неплохо, т.е.

table SpaceQuadrant
{
    ID int not null primary key,
    EntryName varchar(255) not null,
    SpaceQuadrantJoinTableId int not null
                 foreign key references ...anothertable...
}

но любые мысли вообще были бы также приятны, спасибо за чтение!

Дополнительная информация:

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

Если вы считаете, что есть лучший способ определить эти классы, то непременно покажите мне пример, любой язык, с которым вам удобно, - это круто

Решение

Во-первых, специальная поддержка геолокационных данных существует во многих базах данных - могут использоваться различные алгоритмы (например, существует пространственная версия B-дерева), и, вероятно, будет существовать поддержка поиска по близости.

Поскольку у вас есть разные хэш-таблицы для каждого SpaceQuadrant, вам понадобится что-то вроде (отредактировано из сообщения С.Лотта):

table Space {
    SpaceCoordinate,
    Quadrant Foreign Key SpaceQuadrant(ID),
    SpaceObject -- whatever the object is (by ID)
    Primary Key(SpaceCoordinate, Quadrant)
}

Это настоящий (SpaceCoordinate, Quadrant) -> SpaceObjectId словарь.

=====

Теперь, что касается вашей проблемы с производительностью O (1), есть много причин, по которым она рассматривается неправильно.

Вы можете использовать во многих базах данных хэш-индекс для таблиц на основе памяти, как вам кто-то сказал.Но если вам нужно постоянное хранилище, вам нужно будет обновить две таблицы (memory one и persistent one) вместо одной (если для этого нет встроенной поддержки).Чтобы определить, стоит ли это того, вам нужно будет провести сравнительный анализ фактических данных (с фактическими размерами данных).

Кроме того, принудительное сохранение таблицы в памяти может иметь худшие последствия.

Если что-то когда-нибудь поменяется местами, вы покойник - если бы вы использовали B-Дерево (т. е.обычный дисковый индекс), его алгоритмы свели бы к минимуму необходимые операции ввода-вывода.В противном случае все СУБД использовали бы хэш-таблицы и полагались бы на замену, а не на B-деревья.Вы можете попытаться предугадать, впишетесь ли вы в память, но...

Более того, B-деревья - это не O (1), а O (log_512 (N)) или что-то в этом роде (я знаю, что это сводится к O (log N), но поддержите меня в этом).Вам понадобится (2^9)^4 = 2^36 = 64 ГБ, чтобы это было 4, и если у вас так много данных, вам все равно понадобится большой железный сервер, чтобы это поместилось в памяти.Итак, это почти O (1), и постоянные факторы - это то, что действительно имеет значение.
Вы когда-нибудь слышали об алгоритмах низкой асимптотической сложности с большим постоянным коэффициентом, которые были бы быстрее простых только при непрактичных размерах данных?

Наконец, я думаю, что авторы БД умнее нас с вами.Особенно учитывая декларативный характер SQL, ручная оптимизация таким образом не окупится.Если индекс помещается в памяти, я думаю, они могли бы создать и использовать версию индекса диска с хэш-таблицей по мере необходимости, если бы это того стоило.Изучите на этот счет свои документы.

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

Другие советы

Отношения не являются хеш-таблицами; они наборы.

Я бы не организовал базу данных, используя координаты в качестве ключа. Что если объект меняет местоположение? Вместо этого я бы, вероятно, рассматривал координаты как атрибуты объекта.

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

CREATE TABLE SpaceQuadrant (
  quadrant_id INT NOT NULL PRIMARY KEY,
  quadrant_name VARCHAR(20)
  -- other attributes
);

CREATE TABLE SpaceObject (
  object_id INT NOT NULL PRIMARY KEY,
  x NUMERIC(9,2) NOT NULL,
  y NUMERIC(9,2) NOT NULL
  z NUMERIC(9,2) NOT NULL,
  object_name VARCHAR(20) NOT NULL,
  -- other attributes
  quadrant_id INT NOT NULL,
  FOREIGN KEY (quadrant_id) REFERENCES SpaceQuadrant(quadrant_id)
);

В вашем объектно-ориентированном классе непонятно, почему ваши объекты находятся в словаре. Вы упоминаете доступ к ним в O (1) раз, но почему вы делаете это по координатам?

Если вы используете это для оптимизации поиска объектов, которые находятся рядом с определенной точкой (например, космическим кораблем игрока), вы также можете встроить в свой запрос SQL, который заполняет этот SpaceQuadrant, расчет расстояния каждого объекта от данной точки. и отсортировать результаты по расстоянию.

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

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

В этом случае вам понадобится табличный пространственный квадрант с любыми общими (однозначными) атрибутами, которые описывают или характеризуют пространственный квадрант.Таблица SpaceQuadrant будет иметь первичный ключ, возможно, сгенерированный идентификатор, возможно, натуральное значение.Затем хэш-таблица будет состоять из таблицы со значением первичного ключа для перекрестных ссылок на SpaceQuadrant, с позицией (SpaceCoordinate) и атрибутами квадранта и координаты.

Теперь, если у вас есть расширяемая СУБД, вы можете определить пользовательский тип для SpaceCoordinate;в противном случае вы можете использовать три столбца - x, y, z или, например, r, theta, rho - для представления положения (пространственно-координированного).

В общих чертах, структура, которую я описываю, очень похожа на структуру Билла Карвина;ключевое отличие (каламбур не предполагался до тех пор, пока я не перечитал сообщение) заключается в том, что в моей книге совершенно нормально указывать позицию как часть первичного ключа таблицы подчиненных координат, если вы уверены, что это лучший способ ее организации.У вас также может быть столбец идентификатора объекта, который является альтернативным ключом-кандидатом.В качестве альтернативы, если объекты существуют независимо от квадранта пространства, в котором они находятся в данный момент (или могут существовать в нескольких позициях - потому что они не точки, а космические станции или что-то в этом роде), тогда у вас может быть SpaceObject в отдельной таблице.То, что лучше всего, зависит от информации, которой мы не располагаем.

Вы должны быть осведомлены об ограничениях использования SpaceCoordinate как части первичного ключа:

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

То же самое верно и для вашего словаря в памяти;если вы измените координаты, вам придется удалить запись из старого местоположения и поместить ее в новое местоположение в словаре (или язык должен сделать это за вас за кулисами).

Словарь - это таблица. Хеш - это вопрос о том, какой индекс используется. Большинство СУБД предполагают, что таблицы большие и плотно упакованы, поэтому хешированный индекс не подходит.

table SpaceQuadrant { 
    ID Primary Key,
    -- whatever other attributes are relevant
}

table Space {
    SpaceCoordinate Primary Key,
    Quadrant Foreign Key SpaceQuadrant(ID),
    SpaceObject -- whatever the object is
}

Ваши объекты Space имеют ссылки FK на квадрант, в котором они находятся.

В зависимости от вашей РСУБД, вы можете найти хеш-индекс, который даст вам ожидаемую производительность. Например, MySQL, используя механизм хранения HEAP, поддерживает индексы HASH.

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow