Materialized Path - 계층적 데이터 표현...

기타

Materialized Path - 계층적 데이터 표현...

99duuk 2024. 12. 10. 15:28

"메트리얼라이즈드 패스(Materialized Path)"는 계층적 데이터를 표현하고 관리하는 방법 중 하나로, 데이터베이스에서 트리 구조를 구현할 때 사용됨

노드의 경로를 문자열로 저장하여 계층적 구조를 쉽게 표현함

메트리얼라이즈드 패스란?

계층 구조의 각 노드가 루트에서 자신까지의 경로를 문자열 형태로 저장
이 문자열은 일반적으로 특정 구분자를 사용하여 부모-자식 관계 나타냄
트리의 각 노드에서 부모를 빠르게 식별할 수 있으며, SQL의 LIKE나 문자열 연산을 사용해 하위 노드를 쉽게 조회

재귀의 문제점 극복

전통적으로 계층적 데이터를 데이터베이스에서 관리하려면 재귀적 접근(e.g., Adjacency List 방식)으로 트리의 부모-자식 관계를 탐색해야 했습니다. 그러나 이러한 방식은 몇 가지 문제가 있습니다:

복잡한 쿼리:
- 부모-자식 관계를 따라가며 데이터베이스에 반복적으로 접근해야 함.
- SQL에서 WITH RECURSIVE 같은 기능을 사용해야 하며, 일부 DBMS에서는 지원하지 않음.
성능 문제:
- 트리의 깊이가 깊어질수록 재귀 호출로 인한 오버헤드가 커짐.
- 반복적인 데이터베이스 호출로 인해 성능 저하 발생.

(=> 재귀함수 사용 안하고 like로~~)

회사
├─ 경영지원팀
│  ├─ 인사팀
│  └─ 총무팀
└─ 개발팀
   ├─ 프론트엔드팀
   └─ 백엔드팀

2. SQL로 저장

CREATE TABLE organization (
    id INT PRIMARY KEY,
    name VARCHAR(100),
    path VARCHAR(255)
);

INSERT INTO organization (id, name, path) VALUES
(1, '회사', '1'),
(2, '경영지원팀', '1.2'),
(3, '개발팀', '1.3'),
(4, '인사팀', '1.2.4'),
(5, '총무팀', '1.2.5'),
(6, '프론트엔드팀', '1.3.6'),
(7, '백엔드팀', '1.3.7');

+ '1.2.4' 대신 걍 '회사 > 경영지원팀 > 인사팀' 이렇게 박아버려도 되긴함

하위 노드 조회

특정 부서의 모든 하위 부서를 가져오려면 LIKE 연산자를 사용:

SELECT * FROM organization WHERE path LIKE '1.2%';

결과:

경영지원팀
인사팀
총무팀

최상위 노드 조회

. 이 포함되지 않은 노드가 최상위 노드:

SELECT * FROM organization WHERE path NOT LIKE '%.%';

직속 하위 노드 조회

부모 ID를 기준으로 바로 아래 노드를 가져옴:

SELECT * FROM organization WHERE path LIKE '1.2.%' AND LENGTH(path) - LENGTH(REPLACE(path, '.', '')) = 2;

장점

간단한 구조:
- 트리 구조를 별도의 테이블이나 조인 없이 문자열 하나로 표현.
빠른 조회:
- LIKE 연산자를 사용해 하위 노드를 빠르게 조회 가능.
데이터베이스 독립적:
- 대부분의 관계형 데이터베이스에서 지원.

트리 전체 구조를 한 번에 조회 가능:

경로 데이터를 기반으로 전체 계층 구조를 가져오거나 특정 조건으로 필터링

트리 깊이에 무관한 일정한 성능:

재귀 호출 없이 문자열 기반 연산만 수행하므로, 트리 깊이에 따른 성능 차이가 크지 않음.

단점

데이터 업데이트 어려움:
- 부모 노드가 변경되면 하위 노드의 path를 모두 업데이트해야 함.
경로 길이 제한:
- 트리 깊이에 따라 path 문자열이 길어질 수 있음.
SQL 연산의 복잡성:
- 특정 수준의 노드만 조회하려면 복잡한 문자열 연산이 필요.

메트리얼라이즈드 패스 활용의 핵심 포인트

데이터 추가/수정 시 계산 필요:
- 새로운 노드를 추가하거나 부모를 변경할 때, 해당 노드와 모든 자식 노드의 path를 업데이트해야 합니다.
- 이 문제를 해결하기 위해 프로그램 로직에서 추가적인 처리를 수행해야 합니다.
트리 깊이 제한 고려:
- 경로 문자열의 길이가 데이터베이스의 열 크기 제한을 초과하지 않도록 설계해야 합니다.
- 예를 들어, MySQL의 VARCHAR 열 제한은 65535 바이트입니다.

요놈을 레디스에서 쓴다면

노드 ID와 경로를 키로 사용하고, 각 노드의 데이터를 해시로 저장하는 방식을 고려해볼 수 있겠음

조직도: 회사의 부서 및 팀 구조 관리.
카테고리 트리: 전자상거래에서 상품의 카테고리 계층 관리.
포럼: 게시판의 댓글 트리 구조.
파일 시스템: 디렉터리 및 파일의 계층 구조 관리.

같이 활용할 수 있음