데이터베이스 스키마에서 해시테이블 컬렉션을 어떻게 표현하시겠습니까?

StackOverflow https://stackoverflow.com/questions/449202

문제

데이터베이스 스키마에서 도메인 개체를 생성하려고 시도 중이고 코드에서 도메인 개체에 다음과 같이 해시 테이블/목록 멤버가 있다고 표시된 경우:

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

하지만 어떤 생각이라도 좋을 것 같습니다. 읽어주셔서 감사합니다!

추가 정보:

좋은 답변에 감사드립니다. 이미 대충 훑어봤고 답변하기 전에 각각에 대해 잠시 생각해 보고 싶습니다.

이러한 클래스를 정의하는 더 좋은 방법이 있다고 생각한다면 꼭 예를 보여주세요. 편안하게 사용할 수 있는 언어는 무엇이든 좋습니다.

도움이 되었습니까?

해결책

첫째, 지리 위치 데이터에 대한 전용 지원이 많은 데이터베이스에 존재합니다. 다양한 알고리즘을 사용할 수 있으며(예를 들어 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) 성능 문제에 대해 잘못 다루어진 데에는 많은 이유가 있습니다.

누군가 말했듯이 많은 DB에서 메모리 기반 테이블에 대한 해시 인덱스를 사용할 수 있습니다.그러나 영구 저장소가 필요한 경우 하나가 아닌 두 개의 테이블(메모리 테이블과 영구 테이블)을 업데이트해야 합니다(기본적으로 지원되지 않는 경우).가치가 있는지 알아보려면 실제 데이터(실제 데이터 크기 포함)를 벤치마킹해야 합니다.

또한 테이블을 메모리에 강제로 저장하면 더 나쁜 결과를 초래할 수 있습니다.

만약 무언가가 바뀌면 당신은 죽습니다. B-Tree(예:일반 디스크 기반 인덱스), 해당 알고리즘은 필요한 I/O를 최소화했을 것입니다.그렇지 않으면 모든 DBMS는 B-트리 대신 해시 테이블을 사용하고 스와핑에 의존하게 됩니다.기억에 맞을지 예상해볼 수도 있겠지만...

더욱이, B-트리는 O(1)이 아니라 O(log_512(N)) 또는 이와 유사한 것입니다(O(log N)으로 축소된다는 것을 알고 있지만 이에 대해서는 양해해 주시기 바랍니다).4가 되려면 (2^9)^4 = 2^36 = 64GiB가 필요하며, 데이터가 너무 많으면 메모리에 맞도록 큰 철 서버가 필요합니다.따라서 거의 O(1)이고 상수 요소가 실제로 중요한 것입니다.
비실용적인 데이터 크기에 대해서만 단순한 알고리즘보다 빠른 낮은 점근 복잡도, 큰 상수 인자 알고리즘에 대해 들어본 적이 있습니까?

마지막으로, DB 작성자는 나와 당신보다 더 똑똑하다고 생각합니다.특히 SQL의 선언적 특성을 고려할 때 이러한 방식으로 직접 최적화하는 것은 효과가 없습니다.인덱스가 메모리에 적합하다면 가치가 있다면 필요에 따라 디스크 인덱스의 해시 테이블 버전을 구축하고 사용하도록 선택할 수 있을 것입니다.이에 대한 문서를 조사하십시오.

그러나 결론은 조기 최적화는 악하다는 것입니다. 특히 이런 종류의 경우(표준 SQL 최적화와 달리 우리가 스스로 생각하는 이상한 최적화) 선언적 언어를 사용하는 경우에는 더욱 그렇습니다.

다른 팁

관계는 해시 테이블이 아닙니다.그것들은 세트입니다.

좌표를 키로 사용하여 데이터베이스를 구성하지 않습니다.물체의 위치가 바뀌면 어떻게 되나요?대신에 나는 아마도 좌표를 다음과 같이 취급할 것입니다. 속성 객체의.

또한 고정된 수의 차원(예: 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) 시간에 액세스한다고 언급했는데 왜 좌표로 액세스합니까?

이를 사용하여 특정 지점(예: 플레이어의 우주선) 근처에 있는 개체 찾기를 최적화하는 경우 이 SpaceQuadrant를 채우는 SQL 쿼리에 해당 지점에서 모든 개체의 거리를 계산하여 정렬할 수도 있습니다. 거리별 결과입니다.

나는 이러한 제안이 관련성이 있는지 알 만큼 귀하의 프로그램에 대해 충분히 알지 못합니다.하지만 적어도 데이터를 구성하는 다양한 방법을 생각하게 만들고 있나요?

가장 간단한 경우, 사전에는 테이블의 기본 키에 매핑되는 키가 있습니다. 따라서 키 값을 지정하면 간단한 조회를 통해 일치하는 데이터를 즉시 찾을 수 있습니다.

이 경우 공간 사분면을 설명하거나 특성화하는 일반(단일 값) 속성이 있는 SpaceQuadrant 테이블이 필요합니다.SpaceQuadrant 테이블에는 기본 키, 생성된 ID, 자연 값이 있을 수 있습니다.그런 다음 해시 테이블은 위치(SpaceCoordinate)와 사분면 및 좌표의 속성과 함께 SpaceQuadrant를 상호 참조하기 위한 기본 키 값이 있는 테이블로 구성됩니다.

이제 확장 가능한 DBMS가 있는 경우 SpaceCoordinate에 대한 사용자 정의 유형을 정의할 수 있습니다.그렇지 않은 경우 세 개의 열(예: x, y, z 또는 r, theta, rho)을 사용하여 위치(SpaceCoordinate)를 나타낼 수 있습니다.

일반적으로 내가 설명하는 구조는 Bill Karwin의 구조와 매우 유사합니다.핵심(메시지를 다시 읽을 때까지는 의도하지 않은 말장난) 차이점은 그것이 정리하는 가장 좋은 방법이라고 확신한다면 내 책에서 하위 테이블의 기본 키의 일부로 위치를 갖는 것이 완벽하게 괜찮다는 것입니다. 그것.대체 후보 키인 개체 ID 열이 있을 수도 있습니다.또는 객체가 현재 있는 공간 사분면과 독립적으로 존재하는 경우(또는 점이 아니라 우주 정거장 등이기 때문에 여러 위치에 존재할 수 있음) SpaceObject를 별도의 테이블.무엇이 최선인지는 우리가 이용할 수 없는 정보에 따라 달라집니다.

기본 키의 일부로 SpaceCoordinate를 사용할 때의 제한 사항을 알고 있어야 합니다.

  • 두 객체는 ​​동일한 위치를 차지할 수 없습니다(이를 3D 공간뿐만 아니라 해시 테이블에서도 충돌이라고 함).
  • 위치가 변경되면 키 데이터를 업데이트해야 합니다. 이는 키가 아닌 데이터를 업데이트하는 것보다 비용이 더 많이 듭니다.
  • 근접성 조회는 어려울 것입니다. 정확한 조회는 충분히 쉽습니다.

기억 속의 사전도 마찬가지입니다.좌표를 변경하는 경우 이전 위치에서 레코드를 제거하고 사전의 새 위치에 배치해야 합니다(또는 언어가 뒤에서 이를 수행해야 합니다).

사전 ~이다 테이블.해시는 어떤 종류의 인덱스가 사용되는지에 대한 질문입니다.대부분의 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
}

공간 개체에는 해당 개체가 위치한 사분면에 대한 FK 참조가 있습니다.

RDBMS에 따라 원하는 성능을 제공하는 해시 기반 인덱스를 찾을 수 있습니다.예를 들어 MySQL은 HEAP 스토리지 엔진을 사용하여 HASH 인덱스를 지원합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top