3

如果您尝试在数据库模式中创建域对象，并且在您的代码中说域对象具有哈希表/列表成员，如下所示：

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

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

更多信息：

感谢您提供的出色答案，我只是略读了它们，我想在回复之前花一些时间思考每个问题。

如果你认为有更好的方法来定义这些类，那么一定要给我一个例子，你喜欢的任何语言都很酷

4

4 回答 4

2

关系不是哈希表；它们是集合。

我不会使用坐标作为键来组织数据库。如果一个物体改变了位置怎么办？相反，我可能会将坐标视为对象的属性。

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

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) 时间内访问它们，但你为什么要通过坐标来做到这一点？

如果您使用它来优化查找某个点附近的对象（例如玩家的飞船），您还可以在填充此 SpaceQuadrant 的 SQL 查询中构建每个对象与该给定点的距离的计算，并排序距离结果。

我对您的程序知之甚少，无法知道这些建议是否相关。但它们是否至少让你想到了组织数据的不同方式？

于 2009-01-16T02:03:40.553 回答
2

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

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

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

一般而言，我所描述的结构与比尔·卡尔文的结构非常相似。关键（直到我重读消息之后才打算双关语）不同之处在于，如果您确定这是组织的最佳方式，那么在我的书中将位置作为从属表的主键的一部分是完全可以的它。您可能还有一个作为备选候选键的对象 ID 列。或者，如果对象的存在独立于它们恰好所在的空间象限（或者可以存在于多个位置 - 因为它们不是点而是空间站或其他东西），那么您可能将 SpaceObject 放在单独的表。什么是最好的取决于我们无法获得的信息。

您应该知道使用 SpaceCoordinate 作为主键的一部分的限制：

  • 没有两个对象可以占据相同的位置（这在哈希表和 3D 空间中称为碰撞），
  • 如果位置发生变化，那么您必须更新关键数据，这比更新非关键数据更昂贵，
  • 邻近查找将很困难 - 精确查找很容易。

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

于 2009-01-16T02:56:07.000 回答
2

字典是一张表。哈希是使用哪种索引的问题。大多数 RDBMS 都假设表很大且密集，因此散列索引不合适。

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-16T03:00:03.230 回答
1

首先，在许多数据库中都存在对地理定位数据的专门支持——可以使用不同的算法（例如，存在 B 树的空间版本），并且可能存在对邻近搜索的支持。

由于每个 SpaceQuadrant 都有不同的哈希表，因此您需要类似（从 S.Lott 的帖子编辑）：

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-Tree。你可以试着预测你是否能适应记忆，但是......

此外，B-Trees 不是 O(1)，而是 O(log_512(N))，或者类似的东西（我知道它会崩溃到 O(log N)，但请耐心等待）。你需要 (2^9)^4 = 2^36 = 64GiB 才能达到 4，如果你有这么多的数据，你无论如何都需要一个大的铁服务器来适应内存。所以，它几乎是 O(1)，而常数因素才是真正重要的。
有没有听说过低渐近复杂度、大常数因子的算法，在不切实际的数据大小上，它会比简单的算法更快？

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

但底线是，过早的优化是邪恶的，尤其是当它是这种类型时（我们自己考虑的奇怪优化，而不是标准 SQL 优化），并且使用声明性语言。

于 2009-01-16T04:39:06.947 回答