[SQL] 구체화 된 경로 트리를 정렬?

구체화 된 경로 트리를 정렬?

나는 테이블의 트리 구조를 가지고 있고 그것은 나를 빨리 아이를 찾을 수 있도록 구체화 된 경로를 사용합니다. 그러나, 나는 또 하나의 스레드 포럼 응답으로 기대하는 것처럼, 깊이 우선 결과를 정렬 할 필요가있다.

 id | parent_id | matpath |          created           
----+-----------+---------+----------------------------
  2 |         1 | 1       | 2010-05-08 15:18:37.987544
  3 |         1 | 1       | 2010-05-08 17:38:14.125377
  4 |         1 | 1       | 2010-05-08 17:38:57.26743
  5 |         1 | 1       | 2010-05-08 17:43:28.211708
  7 |         1 | 1       | 2010-05-08 18:18:11.849735
  6 |         2 | 1.2     | 2010-05-08 17:50:43.288759
  9 |         5 | 1.5     | 2010-05-09 14:02:43.818646
  8 |         6 | 1.2.6   | 2010-05-09 14:01:17.632695

그래서 최종 결과는 실제로 다음과 같이 분류한다 :

 id | parent_id | matpath |          created
----+-----------+---------+----------------------------
  2 |         1 | 1       | 2010-05-08 15:18:37.987544
  6 |         2 | 1.2     | 2010-05-08 17:50:43.288759
  8 |         6 | 1.2.6   | 2010-05-09 14:01:17.632695
  3 |         1 | 1       | 2010-05-08 17:38:14.125377
  4 |         1 | 1       | 2010-05-08 17:38:57.26743
  5 |         1 | 1       | 2010-05-08 17:43:28.211708
  9 |         5 | 1.5     | 2010-05-09 14:02:43.818646
  7 |         1 | 1       | 2010-05-08 18:18:11.849735

어떻게 그 밖으로 작동까요? 나는 똑바로 SQL에서 (이 PostgreSQL을 8.4이다) 또는 추가 정보는이 테이블에 추가되어야한다고 할 수 있습니까?

업데이트 : 더 나은 정렬 기준을 설명하려고합니다.

해당 ID '1'상상 '1'로 시작하는 'matpath'와 포럼 및 모든 것에 루트 게시물입니다 해당 게시물의 자식입니다. IDS 그래서 5를 통해 2 일에 직접 응답이며 '1'의 matpaths를 얻을. 그것이 1.2 matpath를 얻을 수 있도록하지만, ID (6)는 1 직접적 회신 2이다. 표에 표시된 모든 ID가 적절한 중첩와 스레드 포럼에 대한 포럼의 구조는 다음과 같이 따라서 주문 요구 사항을 보일 것이라고이 수단 :

* id 1 (root post)
    * id 2
        * id 6
            * id 8
    * id 3
    * id 4
    * id 5
        * id 9
    * id 7

해결법

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

   1.나는 일반적으로 SortPath 같은이라는위한 추가 columnn을 만들 수 있습니다. 그것은 당신이 함께 연결된, 정렬 기준으로 필요로하는 데이터를 포함한다. 그 열은 varchar 형의 것, 그리고 문자열로 분류 얻을. 이 같은:

   나는 일반적으로 SortPath 같은이라는위한 추가 columnn을 만들 수 있습니다. 그것은 당신이 함께 연결된, 정렬 기준으로 필요로하는 데이터를 포함한다. 그 열은 varchar 형의 것, 그리고 문자열로 분류 얻을. 이 같은:

   id | parent_id | matpath |          created            |                   sortpath
   ---+-----------+---------+-----------------------------+--------------------------------------------------------------------------------------
    2 |         1 | 1       | 2010-05-08 15:18:37.987544  | 2010-05-08 15:18:37.987544-2
    6 |         2 | 1.2     | 2010-05-08 17:50:43.288759  | 2010-05-08 15:18:37.987544-2.2010-05-08 17:50:43.288759-6
    8 |         6 | 1.2.6   | 2010-05-09 14:01:17.632695  | 2010-05-08 15:18:37.987544-2.2010-05-08 17:50:43.288759-6.2010-05-09 14:01:17.632695-8
    3 |         1 | 1       | 2010-05-08 17:38:14.125377  | 2010-05-08 17:38:14.125377-3
    4 |         1 | 1       | 2010-05-08 17:38:57.26743   | 2010-05-08 17:38:57.267430-4 
    5 |         1 | 1       | 2010-05-08 17:43:28.211708  | 2010-05-08 17:43:28.211708-5
    9 |         5 | 1.5     | 2010-05-09 14:02:43.818646  | 2010-05-08 17:43:28.211708-5.2010-05-09 14:02:43.818646-9
    7 |         1 | 1       | 2010-05-08 18:18:11.849735  | 2010-05-08 18:18:11.849735-7
   

   몇 가지 여기에서주의해야 할 :

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

   2.나는 당신의 구체화 된 경로를 잘 작성하지 믿습니다.

   나는 당신의 구체화 된 경로를 잘 작성하지 믿습니다.

   어떤 로직이 같은 것들을 정렬받을 수 있나요

   1
   1.2
   1
   1.5
   

   왜 두 번째 1은 첫 번째하지 함께 무엇입니까?

   당신이 있다면

   1
   1.2
   2
   2.5
   

   이것은 사소한 것입니다.

   편집하다: 나는 당신의 예를 살펴 보았다 당신은 행의 구체화 된 경로를 저장하지 않는,하지만 당신은 부모 행의 구체화 된 경로를 저장하고 있습니다. 여기에 행의 구체화 된 경로가 실제처럼 보이게하는 방법입니다. 이상의 9 가지를하지 않았을 경우 일 것이다 matpath에 직접적으로 정렬하면 당신은 그것을로 저장하는 경우 :

    id | parent_id | matpath   |          created
   ----+-----------+-----------+----------------------------
     2 |         1 | 1.2       | 2010-05-08 15:18:37.987544
     6 |         2 | 1.2.6     | 2010-05-08 17:50:43.288759
     8 |         6 | 1.2.6.8   | 2010-05-09 14:01:17.632695
     3 |         1 | 1.3       | 2010-05-08 17:38:14.125377
     4 |         1 | 1.4       | 2010-05-08 17:38:57.26743
     5 |         1 | 1.5       | 2010-05-08 17:43:28.211708
     9 |         5 | 1.5.9     | 2010-05-09 14:02:43.818646
     7 |         1 | 1.7       | 2010-05-08 18:18:11.849735
   

   그렇지 않으면 (> 9) 당신이 뭔가에 matpath을 설정해야 할 것입니다

   001.002.006
   001.002.006.008
   

   그게 999 가지를 지원합니다.

   제발 참고

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

   3.수락 솔루션은 전혀 의미가 왜 있는지 이해가 아니에요. (아이디 년대의 경로를 구체화 단지 패드) 그것은 작동하지만, 더 적은 표준화 및 미치게하다의 솔루션 @보다 (더 많은 디스크 공간, 이상의 인덱스 등) 덜 효율적이다.

   수락 솔루션은 전혀 의미가 왜 있는지 이해가 아니에요. (아이디 년대의 경로를 구체화 단지 패드) 그것은 작동하지만, 더 적은 표준화 및 미치게하다의 솔루션 @보다 (더 많은 디스크 공간, 이상의 인덱스 등) 덜 효율적이다.

   영업 이익이 직면 한 전체 시나리오는 @Unreason 올바르게 지적대로의 이행 경로를 구체화, 사실 (MP) 잘못에서 기인하는 것 같다. 영업 이익은 없습니다 현재 노드에 부모에 MP를 제공하고 있습니다. (대신 기본 키 - - 그 이유 기간을 이용하여이 시간) 허용 된 용액에 SortPath 열은 현재 노드로의 경로를 제공함으로써 실현 이것을 보정한다.

   참고로 다음 발췌을 고려 :

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

   4.작품 패딩에 대한 미치게하다의 대답 @ 있지만, 나는이 문제에 대한 내 자신의 발명이라고 생각 다른 솔루션을 제공하고 싶습니다.

   작품 패딩에 대한 미치게하다의 대답 @ 있지만, 나는이 문제에 대한 내 자신의 발명이라고 생각 다른 솔루션을 제공하고 싶습니다.

   넌 b_i는 바이트 인 바이트 스트림, F (X) = b_1b_2..b_i (SO에 MatJax 유감없이)를 만드는 기능을 찾고있다. 우리는 두 바이트 스트림이 첫 번째 다른 바이트와 같은 비교 알고있다. 우리는 이러한 기능을 원하는 F (X)

   0과 같은 길이로 패딩은 확실히 쉽게,이 목표를 가져옵니다. 첫 번째 제로 바이트에서 두 개의 숫자, 모양을하고있다.

   스티븐 위 텐스는 (acko.net) 일부 8 년 전 드루팔 코어에 다른 트릭을 소개 : 다른 자리로 문자열의 앞에 자리의 수를 넣어. 그럼 그들이 더 큰 확실히 더 큰 것 같지 않은 경우, 먼저 길이 바이트 봐 : 그래서, 숫자 97685은이 또한 작동 문자 5 9 7 6 8 5가된다. 그건 그렇고, 당신은 두 숫자가 동일한 길이 알고 있습니다. 그는 또한 0-9A-Z가 많은 단지 모든 편지 16 진수와 같은 숫자 인으로 기본 36 개 숫자를 사용했다. 이 인코딩은 최초의 36 개 노드의 2 바이트 다음 1260 세 가지가 필요합니다 ...

   가독성을 위해 그들은 종종 포함되어 있지만, 참고도 패딩이나 필요한 분리를 인코딩이 교활한 변수 길이는 경로를 구체화있다.

   의 numconv가 지원하는 base85 인코딩을하지만 경우 구분 데이터 정렬을 필요로한다. 당신은 여전히 ​​base68가 소문자를 제거하면 94 개 ASCII 문자가 있습니다.

   당신은 '진'필드를 사용한다면 당신은 base256을 수행 할 수 있습니다 대신 단일 바이트로 바이트 스트림의 길이 전체를 앞에 다음 바이트의 일련 번호를 작성하고 코딩하는 교활한의. 이것은 당신이 2 ^ 2048 정도보다 작은 어떤 나무를 인코딩 할 수 있습니다. 최초의 256 개 노드의 경우, 다음 65280 당신은 3 바이트에서 찾고, 2 바이트를 사용하고 있습니다. 이것은 이미 매우 효율적이다.

   I는 utf8encode (x)는 함수를 지명. 그렇게 생각해! 당신은 bitsorting 대신 bytesorting로 내려갈 필요하지만 그 결과는 변경되지 않습니다 : 가장 왼쪽 제로 비트를 찾을 수 있습니다. 다른 문자열이 1이 있다면, 그것은 더 이상 UTF-8 그래서 확실히 더 크다 해당 인코딩 수 있습니다. 그들은 같은 장소에서 첫 번째 제로가 있다면 우리는 우리를 위해 잘 비교 같은 길이의 비트 문자열을 가지고있다.

   즉 좋은 그러나 분리에 대한 것입니다. 미만 억 개 ​​노드를 포함 나무 작동합니다 - 그래서 비트 스트림 31 개 비트 숫자를 처리 할 수있는 만드는 순수 알고리즘으로 그것을 찾고 UTF-8 알고리즘입니다. 귀하의 구체화 된 경로는 잘 비교 UTF-8로 인코딩 된 번호의 비트 스트림이 될 것입니다 : 폐기 가장 왼쪽에있는 동일한 UTF-8로 인코딩 된 숫자 그리고 우리는 이전 단락에서입니다. Q.E.D.

   우리가 분리 또는 접두사 바이트를 필요로하지 않기 때문에, 우리는 65535, 최대 3 바이트의 두 바이트로 그 다음 1920 단일 바이트로 처음 128 개 노드를 인코딩 할 수 있습니다. 4 바이트의 경우, base256는 이길 것이다. 정말 큰 나무의 경우, 바이트 스트림에 2147483647의 인코더로 UTF-8을 처리 할 수 ​​있습니다. 당신은 base2147483647 인코딩으로 사용할 수 있도록 : D를

   요약하면 : UTF-8이 작은 나무가 아니라 훨씬 더 억 개 노드 아래 base256 이상에 가장 적합합니다. 저쪽이 2048 ^ 2까지 정도 접두사 -로 - 길이 base256 승리. 그 접두사 -로 - 길이 base2147483647 승리를 넘어 아무것도 그 이상 없다.

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

   5.나는 똑바로 SQL에서이 작업을 수행 할 수있는 간단한 방법을 생각할 수 없다. 오히려 matpath보다, 나는 NODE_PATH 여기에 사용합니다. NODE_PATH IS matpath || '.'|| ID

   나는 똑바로 SQL에서이 작업을 수행 할 수있는 간단한 방법을 생각할 수 없다. 오히려 matpath보다, 나는 NODE_PATH 여기에 사용합니다. NODE_PATH IS matpath || '.'|| ID

    id | parent_id | node_path |          created           
   ----+-----------+---------+----------------------------
     2 |         1 | 1.2       | 2010-05-08 15:18:37.987544
     3 |         1 | 1.3       | 2010-05-08 17:38:14.125377
     4 |         1 | 1.4       | 2010-05-08 17:38:57.26743
     5 |         1 | 1.5       | 2010-05-08 17:43:28.211708
     7 |         1 | 1.7       | 2010-05-08 18:18:11.849735
     6 |         2 | 1.2.6     | 2010-05-08 17:50:43.288759
     9 |         5 | 1.5.9     | 2010-05-09 14:02:43.818646
     8 |         6 | 1.2.6.8   | 2010-05-09 14:01:17.632695
   

   지금 당신은 당신이 종류를 실행 한 횟수에 의해 정의 된 정렬 필드, NODE_PATH에 따라 나무를 주문하고 싶다.

   split_part에 정렬 plpgsql에서 사용자 지정 재귀 함수 (NODE_PATH는, '.', recursion_depth) 작동합니다. 당신은 split_part에서 NULL 값을 확인 (그 무시)해야합니다.

from https://stackoverflow.com/questions/2797720/sorting-tree-with-a-materialized-path by cc-by-sa and MIT license