[SQL] 트리 구조의 최적화 된 SQL

트리 구조의 최적화 된 SQL

어떻게 당신은 최고의 성능과 데이터베이스에서 트리 구조 데이터를 얻을까요? 예를 들어, 데이터베이스의 폴더 계층 구조를 말한다. 폴더 데이터베이스 행은 ID, 이름 및 ParentID 열이 곳.

당신은 데이터베이스 통화의 양을 최소화 한 번에 모든 데이터를 얻을 코드에서 처리 할 특별한 알고리즘을 사용겠습니까?

아니면 데이터베이스에 많은 호출을 사용하고 종류의 데이터베이스에서 직접 수행 구조를 얻을 것?

아마 데이터베이스 행의 X 양, 계층 깊이 또는 무엇에 따라 다른 답이있다?

편집 : Microsoft SQL Server를 사용하지만, 다른 관점 중 답변이 너무 재미있다.

해결법

1. ==============================

   1.정말 당신이 트리에 액세스하려고하는 방법에 따라 달라집니다.

   정말 당신이 트리에 액세스하려고하는 방법에 따라 달라집니다.

   한 영리한 기술은 모든 노드에게 부모의 ID가 자녀의 예측 문자열 인 문자열 ID를 제공하는 것입니다. 예를 들어, 부모는 '01'이 될 수 있고, 아이들은 '0100', '0101', '0102'를, 것 등 당신이 한 번에 데이터베이스에서 전체 하위 트리를 선택할 수 있습니다이 방법 :

   SELECT * FROM treedata WHERE id LIKE '0101%';
   

   기준 초기 문자열이기 때문에, ID 항목의 인덱스는 쿼리를 가속화한다.

2. ==============================

   2.A는 가장 일반적인 RDMS에 나무를 저장하는 모든 방법 중 인접 목록 및 중첩 된 세트입니다. 읽고 하나의 쿼리에서 전체 트리를 검색 할 수 있습니다에 대한 중첩 된 세트에 최적화되어 있습니다. 인접리스트는 쓰기에 최적화 된 간단한 쿼리에 추가 할 수 있습니다.

   A는 가장 일반적인 RDMS에 나무를 저장하는 모든 방법 중 인접 목록 및 중첩 된 세트입니다. 읽고 하나의 쿼리에서 전체 트리를 검색 할 수 있습니다에 대한 중첩 된 세트에 최적화되어 있습니다. 인접리스트는 쓰기에 최적화 된 간단한 쿼리에 추가 할 수 있습니다.

   인접리스트 각각의 노드 (A)는 부모 노드 나 아이 노드 (다른 링크가 가능하다)를 의미 열을 갖는다. 당신이 부모 자식 관계를 기반으로 계층 구조를 구축 할 수있는 사용. 당신이 당신의 나무의 깊이를 제한 불행하게도하지 않는 한 쿼리에서 모든 것을 끌어와 그것을 읽는 것은 일반적으로 느린을 업데이트보다 수 없습니다.

   역이 참 중첩 된 세트 모델, 읽기는 쉽고 빠르게하지만 당신은 번호 체계를 유지해야하기 때문에 업데이트가 복잡해. 중첩 된 세트 모델은 예약 주문을 기반으로 번호 체계를 사용하여 모든 노드를 열거하여 혈통 및 정렬 순서를 모두 암호화한다.

   나는 중첩 된 집합 모델을 사용하고 복잡하면서 가치가 큰 계층 구조를 최적화 읽기했습니다. 당신이 노드를 트리를 인출 및 번호 매기기에 몇 가지 운동을하면 당신은 그것의 묘리를 터득해야한다.

   MySQL의 계층 적 데이터 관리 :이 방법에 대한 나의 연구는이 문서에서 시작했다.

3. ==============================

   3.우리의 제품 I 작업에서 SQL Server에 저장된 일부 트리 구조를 가지고 레코드에 노드의 계층 구조를 저장할 위에서 언급 한 기술을 사용합니다. 즉

   우리의 제품 I 작업에서 SQL Server에 저장된 일부 트리 구조를 가지고 레코드에 노드의 계층 구조를 저장할 위에서 언급 한 기술을 사용합니다. 즉

   tblTreeNode
   TreeID = 1
   TreeNodeID = 100
   ParentTreeNodeID = 99
   Hierarchy = ".33.59.99.100."
   [...] (actual data payload for node)
   

   하여 계층 구조를 유지하는 것은 물론 까다로운 비트이며 차종은 트리거의 사용합니다. 부모 또는 자녀의 계층 구조는 당신이 필요로하는 모든 정보를 가지고 있기 때문에 삽입 / 삭제 / 이동을 생성하는, 결코 재귀입니다.

   당신은 노드의 자손을 모두 thusly 히 얻을 수 있습니다 :

   SELECT * FROM tblNode WHERE Hierarchy LIKE '%.100.%'
   

   여기에 삽입 트리거는 다음과 같습니다

   --Setup the top level if there is any
   UPDATE T 
   SET T.TreeNodeHierarchy = '.' + CONVERT(nvarchar(10), T.TreeNodeID) + '.'
   FROM tblTreeNode AS T
       INNER JOIN inserted i ON T.TreeNodeID = i.TreeNodeID
   WHERE (i.ParentTreeNodeID IS NULL) AND (i.TreeNodeHierarchy IS NULL)
   
   WHILE EXISTS (SELECT * FROM tblTreeNode WHERE TreeNodeHierarchy IS NULL)
       BEGIN
           --Update those items that we have enough information to update - parent has text in Hierarchy
           UPDATE CHILD 
           SET CHILD.TreeNodeHierarchy = PARENT.TreeNodeHierarchy + CONVERT(nvarchar(10),CHILD.TreeNodeID) + '.'
           FROM tblTreeNode AS CHILD 
               INNER JOIN tblTreeNode AS PARENT ON CHILD.ParentTreeNodeID = PARENT.TreeNodeID
           WHERE (CHILD.TreeNodeHierarchy IS NULL) AND (PARENT.TreeNodeHierarchy IS NOT NULL)
       END
   

   여기에 업데이트 트리거는 다음과 같습니다

   --Only want to do something if Parent IDs were changed
   IF UPDATE(ParentTreeNodeID)
       BEGIN
           --Update the changed items to reflect their new parents
           UPDATE CHILD
           SET CHILD.TreeNodeHierarchy = CASE WHEN PARENT.TreeNodeID IS NULL THEN '.' + CONVERT(nvarchar,CHILD.TreeNodeID) + '.' ELSE PARENT.TreeNodeHierarchy + CONVERT(nvarchar, CHILD.TreeNodeID) + '.' END
           FROM tblTreeNode AS CHILD 
               INNER JOIN inserted AS I ON CHILD.TreeNodeID = I.TreeNodeID
               LEFT JOIN tblTreeNode AS PARENT ON CHILD.ParentTreeNodeID = PARENT.TreeNodeID
   
           --Now update any sub items of the changed rows if any exist
           IF EXISTS (
                   SELECT * 
                   FROM tblTreeNode 
                       INNER JOIN deleted ON tblTreeNode.ParentTreeNodeID = deleted.TreeNodeID
               )
               UPDATE CHILD 
               SET CHILD.TreeNodeHierarchy = NEWPARENT.TreeNodeHierarchy + RIGHT(CHILD.TreeNodeHierarchy, LEN(CHILD.TreeNodeHierarchy) - LEN(OLDPARENT.TreeNodeHierarchy))
               FROM tblTreeNode AS CHILD 
                   INNER JOIN deleted AS OLDPARENT ON CHILD.TreeNodeHierarchy LIKE (OLDPARENT.TreeNodeHierarchy + '%')
                   INNER JOIN tblTreeNode AS NEWPARENT ON OLDPARENT.TreeNodeID = NEWPARENT.TreeNodeID
   
       END
   

   하나 이상의 비트, 체크 제약 트리 노드에서 순환 참조를 방지하기 위해 :

   ALTER TABLE [dbo].[tblTreeNode]  WITH NOCHECK ADD  CONSTRAINT [CK_tblTreeNode_TreeNodeHierarchy] CHECK  
   ((charindex(('.' + convert(nvarchar(10),[TreeNodeID]) + '.'),[TreeNodeHierarchy],(charindex(('.' + convert(nvarchar(10),[TreeNodeID]) + '.'),[TreeNodeHierarchy]) + 1)) = 0))
   

   또한 트리거는 트리 당 하나 개 이상의 루트 노드 (null의 부모)을 방지하고, 다른 TreeIDs에 속하는에서 관련 노드를 유지하는 것이 좋습니다 (하지만 그 조금 더 사소한 위보다.)

   이 솔루션은 수용 가능한 수행하는 경우 확인하려면 특별한 경우를 확인하는 것이 좋습니다. 도움이 되었기를 바랍니다!

4. ==============================

   4.Celko는 (2000)이 쓴 :

   Celko는 (2000)이 쓴 :

   http://www.dbmsmag.com/9603d06.html

   http://www.intelligententerprise.com/001020/celko1_1.jhtml;jsessionid=3DFR02341QLDEQSNDLRSKHSCJUNN2JVN?_requestid=32818

   다른 사람 질문 :

   오라클 트리 쿼리에서 다른 테이블에 가입

   나무 사용하여 SQL에서 값의 합계를 계산하는 방법

   어떻게 데이터베이스에 디렉토리 / 계층 / 트리 구조를 저장?

   MYSQL에서 재귀 저장 프로 시저의 성능은 계층 적 데이터를 얻을 수 있습니다

   나무에 평평한 테이블을 구문 분석하는 가장 효율적인 / 우아한 방법은 무엇입니까?

   마지막으로, 당신은 레일 "acts_as_tree"(읽기 무거운)와 "acts_as_nested_set"(쓰기 무거운) 플러그인을 볼 수 있었다. 나는 그들을 비교하는 좋은 링크를 ahve하지 않습니다.

5. ==============================

   5.계층 구조에 대한 쿼리의 몇 가지 일반적인 종류가 있습니다. 쿼리의 대부분의 다른 종류 다음에 변화이다.

   계층 구조에 대한 쿼리의 몇 가지 일반적인 종류가 있습니다. 쿼리의 대부분의 다른 종류 다음에 변화이다.

   의 (a)의 경우 (특정 깊이)는 SQL에서 쉽다. 특별한 경우 (깊이 = 1) SQL에서 사소한입니다. 비 제로 깊이는 어렵습니다. 유한하지만 비 제로 깊이는,의 조인 유한 번호를 통해 수행 할 수 있습니다. 무기한 깊이 (위로, 아래로)을 (b)의 경우는 정말 어렵다.

   당신이 나무는 거대한 (노드의 수백만)의 경우, 당신은 더 당신이하려고 어떤 문제가 상처의 세계에있어 않습니다.

   당신의 나무가 만 노드에 해당되는 경우, 단지 모든 거기에 메모리 및 작업로를 가져옵니다. 인생은 OO의 세계에서 훨씬 간단합니다. 간단하게 행을 가져오고 행이 반환 될 때 트리를 구축 할 수 있습니다.

   당신이 거대한 나무가 있다면, 당신은 두 가지 선택이있다.

6. ==============================

   6.데이터베이스에 많은 나무가 있고, 당신은 오직 전체 트리의 출력을 얻을 경우, 나는 모든 노드를 얻을, 트리 ID (또는 루트 노드 ID) 및 데이터베이스의 각 노드에 대한 부모 노드의 ID를 저장하는 것 메모리의 특정 트리 ID 및 프로세스.

   데이터베이스에 많은 나무가 있고, 당신은 오직 전체 트리의 출력을 얻을 경우, 나는 모든 노드를 얻을, 트리 ID (또는 루트 노드 ID) 및 데이터베이스의 각 노드에 대한 부모 노드의 ID를 저장하는 것 메모리의 특정 트리 ID 및 프로세스.

   당신이 하위 트리를 받고있을 것이다 그러나 경우 중 하나 필요는 위의 방법을 사용하여 각 노드의 모든 부모 노드를 저장 할 수 있도록, 당신은 단지 특정 부모 노드 ID의 하위 트리를 얻을 수 있습니다, 또는 당신이에 내려으로 여러 SQL 쿼리를 수행 나무 (희망 당신의 나무에는 사이클이 없습니다!), 그것은 수도 있도록, 다시 컴파일 SQL을 방지하기 위해 (노드가 동일한 유형이고 모두 하나의 테이블에 저장되어 있다고 가정) 같은 준비된 명령문을 재사용 할 수 있지만, 하지 데이터베이스 최적화 쿼리로하는 것이 바람직 할 수있다 적용 참으로, 속도가 느려질 수. 찾아 몇 가지 검사를 실행할 수 있습니다.

   당신은 단지 하나의 트리를 저장하는 경우, 귀하의 질문은 질의 하위 트리 중 하나가되고, 두 번째 대답은 적용.

7. ==============================

   7."실현 경로"또는 "유전자 나무"에 대한 구글 ...

   "실현 경로"또는 "유전자 나무"에 대한 구글 ...

8. ==============================

   8.오라클에서 SELECT ... CONNECT 나무를 검색 할 수 BY 문이있다.

   오라클에서 SELECT ... CONNECT 나무를 검색 할 수 BY 문이있다.

9. ==============================

   9.I는 parentID와 관련된 ID를 저장하는 간단한 방법의 팬이다 :

   I는 parentID와 관련된 ID를 저장하는 간단한 방법의 팬이다 :

   ID     ParentID
   1      null
   2      null
   3      1
   4      2
   ...    ...
   

   유지 관리가 용이하고, 확장 성이있다.

10. ==============================

    10.그것은 몇 가지 검색 방법뿐만 아니라 파생 열로 계보를 저장하는 방법을 보여줍니다으로이 문서는 흥미 롭다. 계보는 너무 많은 조인없이 계층 구조를 검색하는 바로 가기 방법을 제공합니다.

    그것은 몇 가지 검색 방법뿐만 아니라 파생 열로 계보를 저장하는 방법을 보여줍니다으로이 문서는 흥미 롭다. 계보는 너무 많은 조인없이 계층 구조를 검색하는 바로 가기 방법을 제공합니다.

11. ==============================

    11.모든 상황에 대한 작업에 가고 있지만, 예를 들어 주석 구조를 제공 :

    모든 상황에 대한 작업에 가고 있지만, 예를 들어 주석 구조를 제공 :

    ID | ParentCommentID
    

    또한 최상위 코멘트를 나타냅니다 TopCommentID을 저장할 수 :

    ID | ParentCommentID | TopCommentID
    

    이 최상위 코멘트의 경우 TopCommentID 및 ParentCommentID가 null 또는 0 곳. 맨 위의 부모에 대한 자녀의 의견, 위의 코멘트에 ParentCommentID 포인트 및 TopCommentID 포인트.

from https://stackoverflow.com/questions/317322/optimized-sql-for-tree-structures by cc-by-sa and MIT license