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

Question

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

public class SpaceQuadrant : PersistentObject
{

    public SpaceQuadrant()
    {
    }

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

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

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

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

но любые мысли тоже были бы хорошими, спасибо за чтение!

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

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

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

Answer 1

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

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

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

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

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

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

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

Answer 2

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

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
}

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

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

Answer 3

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

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

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

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, расчет расстояния каждого объекта от данной точки и отсортировать результаты по расстоянию.

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

Answer 4

Во-первых, во многих базах данных существует специальная поддержка гео-локализованных данных - можно использовать разные алгоритмы (например, существует пространственная версия 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), есть много причин, почему она ошибочно решена.

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

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

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

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

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

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