如何在数据库模式中表示哈希表集合？

如果你试图创建数据库模式中的域对象，并在代码中说的域对象有一个哈希表/列表成员，像这样：如何在数据库模式中表示哈希表集合？

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... 
}

但任何想法都会很好，谢谢阅读！

更多信息：

感谢伟大的答案，已经，我只有脱脂他们，我需要一些时间思考我每次回应前。

如果你想有更好的方式来定义这些类，然后通过各种手段告诉我一个例子，你的舒适，任何语言是酷

来源

2009-01-16 Mark Rogers

你能提供关于这个问题的更多信息吗？例如，您的坐标系中有多少个尺寸？你期望有多少个象限？（根据定义，是不是只有四个？）。空间是否总是被象限访问？ – Uri 2009-01-16 01:35:19

首先，在许多数据库中都存在对地理位置数据的专用支持 - 可以使用不同的算法（例如，存在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（即正常的基于磁盘的索引），它的算法将会最小化所需的I/O。否则，所有DBMS将使用散列表并依赖交换，而不是B-Trees。你可以尝试预测你是否适合内存，但...

此外，B-树不是O（1），但它们是O（log_512（N）），或类似的东西（我知道那崩溃到O（日志N），但承担我）。你需要（2^9）^ 4 = 2^36 = 64GiB为4，如果你有这么多的数据，你需要一个大型的铁服务器，以适应内存。所以，这几乎是O（1），而常数因素才是真正重要的。
有没有听说过低渐近复杂度，大常数因子算法，这会比仅仅在不实用数据大小上的简单算法更快？

最后，我认为DB作者比我和你更聪明。特别是考虑到SQL的声明性质，用这种方式手工优化它并不会付出代价。如果索引适合内存，我想他们可以根据需要选择构建和使用散列表版本的磁盘索引，如果它值得的话。为此调查你的文档。

但底线是，过早优化是邪恶的，特别是当它是这种类型（奇怪的优化我们正在考虑自己，而不是标准的SQL优化）和声明性语言。

来源

2009-01-16 04:39:06 Blaisorblade

关系不是哈希表;他们是集合。

我不会使用坐标作为关键字来组织数据库。如果对象更改位置会怎样？相反，我可能会将对象的坐标视为属性。

此外，我假设有一个固定的维数，例如三个。如果是这样，那么你可以将对象的这些属性存储在固定列：

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，计算每个对象与给定对象的距离点，并按距离排序结果。

我对您的计划了解不多，无法确定这些建议是否相关。但是他们至少让你想到组织数据的不同方式？

来源

2009-01-16 02:03:40

以这种方式进行邻近搜索会很慢 - 您不能使用索引，它是全表扫描和计算。对地理位置的支持可以使其更快。 – Blaisorblade 2009-01-16 04:23:24

现在OP正在做的方式是，无论如何，在他可以从他的O（1）散列搜索中受益之前，他必须加载表的全部内容，不是吗？ – 2009-01-16 05:59:45

在最简单的情况下，字典有一个映射到表的主键的键 - 这样，当您指定键的值时，可以通过简单的查找立即找到匹配的数据。

在这种情况下，您需要一个SpaceQuadrant表以及用于描述或表征空间象限的任何常规（单值）属性。 SpaceQuadrant表将有一个主键，可能是一个生成的ID，可能是一个自然值。散列表将包含一个表，其中包含用于交叉引用SpaceQuadrant的主键值，位置（SpaceCoordinate）以及象限和坐标的属性。

现在，如果您有可扩展的DBMS，则可以为SpaceCoordinate定义用户定义的类型;否则，您可以使用三个列（例如x，y，z或r，theta，rho）来表示位置（SpaceCoordinate）。

一般而言，我所描述的结构与比尔卡尔文的比较相似;关键是（在我重读消息之前，双关语并不打算）区别在于，如果您确定这是组织的最佳方式，那么在本书中将该位置作为副纵坐标表的主键的一部分是完全可以的它。您可能还有一个对象ID列，这是一个替代候选键。或者，如果物体存在一个独立于空间象限的存在，它们恰好在此刻存在（或者可以存在于多个位置 - 因为它们不是点，而是空间站或某物），那么您可能将SpaceObject放置在单独的桌子。什么是最好的取决于我们没有的信息。

你应该意识到使用SpaceCoordinate作为主键的一部分的局限性：

没有两个对象可以占据相同的位置（这就是所谓的在哈希表的碰撞，以及在3D空间），
如果位置发生变化，那么您必须更新密钥数据，这比更新非关键数据更昂贵，因此近似查找将很难 - 精确查找很容易。

你的字典在内存中也是如此;如果更改坐标，则必须从旧位置移除记录，并将其放在字典中的新位置（或者语言必须在幕后为您执行此操作）。

来源

2009-01-16 02:56:07

词典是的一张表。散列是一个什么样的索引被使用的问题。大多数关系型数据库管理系统假设表格大而密集，使得散列索引不合适。

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引用。

根据您的RDBMS，您可能能够找到一个基于散列的索引，从而获得您所期望的性能。例如MySQL，使用HEAP存储引擎支持HASH索引。

来源

2009-01-16 03:00:03

如何在数据库模式中表示哈希表集合？

回答

相关问题