트리 데이터를 저장하는 빠른 관계형 메서드 (예 : 기사에 스레드 된 주석)

Question

기사에 대한 주석을 저장하는 CMS가 있습니다. 이 주석은 스레드 및 비 스레드 모두 일 수 있습니다. 기술적으로는 회신 열이 공백 인 채 스레드되지 않은 경우와 동일합니다. 내 응용 프로그램은 sqlLite, MySQL 및 pgsql에서 작동하므로 표준 SQL이 상당히 필요합니다.

나는 현재

comment_id 
article_id 
user_id 
comment 
timestamp 
thread (this is the reply column) 

내 질문에 가장 데이터베이스의 스레드 의견을 표현하는 방법을 알아 내기 위해 코멘트 테이블을 가지고있다. 아마도 내용이없는 트리 세트와 텍스트를 보관할 간단한 테이블을 지원하는 별도의 테이블에 있을까요? 아마도 이미 그렇 겠지? 아마도 다른 방법일까요?

주석이 스레드되지 않은 경우 나는 타임 스탬프로 쉽게 주문할 수 있습니다.

당신이 ORDER BY에서 볼 수 있듯이 그들은이

ORDER BY SUBSTRING(c.thread, 1, (LENGTH(c.thread) - 1)) 

같은 종류의 I를 스레드하는 경우 함수 기반 인덱스는 정말 오라클에 살고있는 한, 주석 쿼리 적 인덱스를 사용하지 않습니다. 번쩍이는 빠른 코멘트 페이지를 갖도록 도와주세요.

Answer 1

나는 정말 어떻게 Drupal이이 문제를 해결 하는지를 좋아합니다. 스레드 ID를 각 주석에 할당합니다. 이 ID는 첫 번째 주석의 경우 1에서 시작합니다. 이 주석에 응답이 추가되면 id 1.1이 할당됩니다. 덧글 1.1에 대한 답장은 스레드 id 1.1.1가 주어집니다. 덧글 1.1의 형제는 스레드 id가 1.2 주어집니다. 당신은 아이디어를 얻습니다. 이 스레드 ID 계산은 주석을 추가 할 때 하나의 쿼리로 쉽게 수행 할 수 있습니다.

스레드가 렌더링되면 스레드에 속한 모든 주석이 스레드 ID별로 정렬 된 단일 쿼리로 반입됩니다. 그러면 스레드가 오름차순으로 제공됩니다. 또한 스레드 id를 사용하여 각 주석의 중첩 수준을 찾아 적절히 들여 쓸 수 있습니다.

1 
1.1 
1.1.1 
1.2 
1.2.1 

는 분류하는 몇 가지 문제가 있습니다 : 스레드 ID의 한 구성 요소가이 개 자리에 성장

• 경우, 스레드 ID별로 정렬하면 예상 순서를 생산하지 않습니다. 쉬운 해결책은 스레드 ID의 모든 구성 요소가 동일한 너비를 갖도록 0으로 채워지는 것입니다.
• 스레드 ID를 내림차순으로 정렬해도 예상 내림차순이 생성되지 않습니다.

Drupal은 vancode라는 번호 체계를 사용하여보다 복잡한 방식으로 첫 번째 문제를 해결합니다. 두 번째 문제는 내림차순으로 정렬 할 때 백 슬래시 (ASCII 코드가 자릿수보다 큼)를 스레드 ID에 추가하여 해결됩니다. comments module의 소스 코드를 확인하여이 구현에 대한 자세한 내용을 확인할 수 있습니다 (comment_get_thread 함수 앞에있는 큰 주석 참조).

Answer 2

나는 실제로 이것을 직접했다. 관계형 데이터베이스에서 계층 적 데이터를 나타내는 중첩 된 집합 모델을 사용했습니다.

Managing Hierarchical Data in MySQL은 저에게 순수한 금이었습니다. 중첩 세트는 해당 기사에서 설명 된 두 번째 모델입니다.

Answer 3

사실 실제로는 읽기와 쓰기의 균형이 있어야합니다.

모든 삽입에서 많은 수의 행을 업데이트하는 것이 좋으면 중첩 된 세트 (또는 이와 동등한 세트)를 사용하면 쉽고 빠르게 읽을 수 있습니다.

그 외의 경우, 부모의 간단한 FK는 매우 간단한 삽입 기능을 제공하지만 검색시 악몽 일 수 있습니다.

중첩 된 세트로 이동하지만 예상되는 데이터 볼륨과 사용 패턴에주의해야한다고 생각합니다. (각 업데이트에 대해 두 개의 인덱싱 된 열 (왼쪽 및 오른쪽 정보 용)에 행이 여러 개, 어떤 시점에서 문제가 될 수 있음).

Answer 4

인접성과 중첩 세트 모델 중 하나를 선택할 수 있습니다. 기사 Managing Hierarchical Data in MySQL은 좋은 소개를합니다.

이론적 인 토론은 Celko의 Trees and Hierarchies을 참조하십시오.

데이터베이스가 윈도우 기능을 지원하는 경우 스레드 목록을 구현하는 것이 다소 쉽습니다.

이

create Tablename (
    RecordID integer not null default 0 auto_increment, 
    ParentID integer default null references RecordID, 
    ... 
) 

그런 다음 스레드보기를 표시 재귀 공통 테이블 표현식을 사용할 수 있습니다 : 당신이 필요로하는 등 대상 데이터베이스 테이블의 순환 참조입니다. 예를 들어 here을 사용할 수 있습니다.

Answer 5

불행히도이를 수행하기위한 순수 SQL 메소드는 매우 느립니다.

@Marc W이 제안한 NESTED SETS은 매우 우아하지만 나뭇 가지가 범위를 벗어나는 경우 전체 트리를 업데이트해야 할 수 있습니다.

은 MySQL에서 빨리 작업을 수행하는 방법에 대한 내 블로그에서이 문서를 참조하십시오 :

• Hierarchical queries in MySQL - 모방을 Oracle의 CONNECT BY

만들 수있는 기능이 필요합니다

:

을

CREATE FUNCTION hierarchy_connect_by_parent_eq_prior_id(value INT) RETURNS INT 
NOT DETERMINISTIC 
READS SQL DATA 
BEGIN 
     DECLARE _id INT; 
     DECLARE _parent INT; 
     DECLARE _next INT; 
     DECLARE CONTINUE HANDLER FOR NOT FOUND SET @id = NULL; 

     SET _parent = @id; 
     SET _id = -1; 

     IF @id IS NULL THEN 
       RETURN NULL; 
     END IF; 

     LOOP 
       SELECT MIN(id) 
       INTO @id 
       FROM t_hierarchy 
       WHERE parent = _parent 
         AND id > _id; 
       IF @id IS NOT NULL OR _parent = @start_with THEN 
         SET @level = @level + 1; 
         RETURN @id; 
       END IF; 
       SET @level := @level - 1; 
       SELECT id, parent 
       INTO _id, _parent 
       FROM t_hierarchy 
       WHERE id = _parent; 
     END LOOP; 
END 

과 같은 검색어로 사용하십시오.

SELECT hi.* 
FROM (
     SELECT hierarchy_connect_by_parent_eq_prior_id(id) AS id, @level AS level 
     FROM (
       SELECT @start_with := 0, 
         @id := @start_with, 
         @level := 0 
       ) vars, t_hierarchy 
     WHERE @id IS NOT NULL 
     ) ho 
JOIN t_hierarchy hi 
ON  hi.id = ho.id 

물론 이것은 MySQL이지만 실제로 빠릅니다. 당신이 PostgreSQL 및 MySQL 타협 이식을 원하는 경우

, 당신은 CONNECT BY에 대한 PostgreSQL 년대에있는 contrib를 사용하여 두 시스템에 같은 이름의 저장 프로 시저로 쿼리를 포장 할 수 있습니다.

Answer 6

나는 대답은 조금 늦게 알고 있지만, 나무에 대한 데이터는 폐쇄 테이블 http://www.slideshare.net/billkarwin/models-for-hierarchical-data

그것은 4 가지 방법을 설명합니다 사용

• Adjcency 목록 (단순한 부모 외래 키)
• 에게 경로 열거 (수용된 대답에 언급 된 Drupal 전략)
• 중첩 세트
• 폐쇄 테이블 토르/후손의 사실을 별도의 관계로 [표], 가능한 거리 열 포함)

마지막 옵션은 다른 것과 비교하여 CRUD 작업이 쉽다는 장점이 있습니다. 비용은 공간이며, 최악의 경우 숫자 트리 노드에서 O (n^2) 크기이지만 실제로는 그렇게 나쁘지는 않습니다.