99클럽 TIL

99클럽 코테 스터디 8일차 TIL DB R-Tree

차가리 2024. 5. 27. 20:51
728x90
  • DB
    • Index
      • Index 작동 원리
      • Index 종류
        • B-Tree 인덱스
        • Hash Indexes
        • Bitmap Index
        • GIST(Generalized Search Tree)
        • R-Tree
        • Full Text Index
        • Spatial Index
        • Trie(Prefix Tree) Index
        • Covering Index
    • 영속성
    • 트랜잭션
    • ORM
    • ACID
    • N+1 문제
    • DB 정규화
    • Data Replication
    • sharding 전략
    • CAP 이론

란?

  • 다차원 공간 데이터를 인덱싱하기 위한 트리 기반 자료구조
  • 특히 지리적 정보 시스템(GIS), CAD 시스템, 이미지 및 멀티미디어 데이터베이스 등에 많이 사용됨.
  • R-Tree 는 공간 객체(점,선, 다각형 등)를 사각형 경계 상자(bounding box) 로 감싸고, 이러한 경계 상자를 중첩하여 계층적으로 구성함. 이 구조는 공간 검색 쿼리(예 : 영역 검색, 근접 검색 등)를 효율적으로 처리할 수 있게 해줌.
    ex) 내 위치에서 2km 이내에 있는 모든 도로 구간 검색, 내 현재 위치에서 2km 이내에 있는 모든 박물관 찾기

![[Pasted image 20240516163407.png]]
![[Pasted image 20240516163539.png]]

R-Tree 구조

  • R-Tree 는 B-Tree 와 유사하게 균형 트리 구조를 가짐.
    • B-Tree 는 1차원 데이터를 다루는 반면, R-Tree는 다차원 데이터를 다룸.

구조적 요소

  • 리프 노드(Leaf Node) : 실제 데이터 객체의 경계 상자를 포함함.
  • 비리프 노드(Non-Leaf Node)
    • 자식 노드의 경계 상자를 포함함. 비리프 노드는 자식 노드들을 감싸는 최소 경계 상자(MBR, Minimum Bounding Rectangle) 을 가짐.

R-Tree 동작

R-Tree 는 삽입, 삭제, 검색 연산을 지원함. 각 연산은 트리의 구조적 특성을 유지하면서 수행됨.

삽입(Insertion)

  1. 적절한 리프 노드 선택
    • 새로운 객체를 삽입할 적절한 리프 노드를 찾음. 이때, 객체를 삽입했을 때 최소한의 면적 증가가 발생하는 노드를 선택함.
  2. 객체 삽입
    • 선택된 리프 노드에 객체를 삽입함. 리프 노드가 가득 찬 경우 분할(split) 연산을 수행함.
  3. 노드 분할
    • 리프 노드가 가득 차면, 노드를 두 개의 노드로 분할함. 이 과정은 비리프 노드에서도 동일하게 적용됨.
  4. 상위 노드 갱신
    • 삽입 후, 상위 노드들의 경계 상자를 갱신함.

삭제(Deletion)

  1. 적절한 리프 노드 선택
    • 삭제할 객체를 포함하는 리프 노드를 찾음.
  2. 객체 삭제
    • 해당 리프 노드에서 객체를 삭제함. 리프 노드의 객체 수가 너무 적으면 병합(Merge) 연산을 수행함.
  3. 노드 병합
    • 리프 노드의 객체 수가 특정 임계값 이하로 떨어지면, 해당 노드를 다른 노드와 병합하거나 트리에서 제거함.
  4. 상위 노드 갱신
    • 삭제 후, 상위 노드들의 경계 상자를 갱신함.

검색(Search)

  1. 루트 노드에서 시작
    • 루트 노드에서 검색을 시작함.
  2. 경계 상자 비교
    • 각 노드의 경계 상자와 검색 조건을 비교함.
  3. 재귀적 탐색
    • 검색 조건과 겹치는 경계 상자를 가진 노드를 재귀적으로 탐색함.
  4. 리프 노드 도달
    • 리프 노드에 도달하면 실제 데이터 객체와 검색 조건을 비교하여 결과를 반환함.

R-Tree 의 예

구조와 동작을 설명

초기 데이터 삽입

  1. 포인트 데이터를 R-Tree 에 삽입. 각 포인트는 경계 상자로 감싸지며, 리프 노드에 저장됨.
Points: (1,1), (3,2), (6,3), (5,5), (7,8),(8,6)
  1. 첫 번째 포인트 (1,1) 을 삽입함. 새로운 리프 노드가 생성되고 (1,1)이 포함됨.
Root
 └── (1,1)
  1. 두 번째 포인트 (3,2) 를 삽입함. 현재 리프 노드의 경계 상자가 갱신됨.
Root
 └── (1,1), (3,2)
  1. 세 번째 포인트 (6,3) 을 삽입함. 리프 노드가 가득 찼으므로, 분할 연산이 발생함.
Root
 ├── (1,1), (3,2)
 └── (6,3)
  1. 나머지 포인트들을 차례대로 삽입함. 리프 노드가 가득 차면 분할 연산이 발생하며, 상위 노드의 경계 상자가 갱신됨.
Root
 ├── (1,1), (3,2)
 ├── (6,3), (5,5)
 └── (7,8), (8,6)

검색

  1. 특정 범위 내의 포인트를 검색함. 예를 들어 (2,1)에서 (7,4) 내의 포인트를 검색함.
  2. 루트 노드에서 검색을 시작함. 각 자식 노드의 경계 상자와 검색 범위를 비교함.
Search range: (2,1) - (7,4)
  1. 각 리프 노드에서 검색 범위와 겹치는 포인트를 찾음.
Result: (3,2), (6,3)

장단점

장점

  1. 효율적인 공간 검색
    • R-Tree 는 다차원 공간 데이터에 대한 효율적인 검색을 지원함.
  2. 동적 데이터 지원
    • 삽입과 삭제 연산을 통해 동적으로 데이터를 관리할 수 있음.
  3. 다양한 응용 분야
    • GIS,CAD, 멀티미디어 데이터베이스 등 다양한 분야에서 활용 가능함.

단점

  1. 복잡한 구현
    • R-Tree의 분할 및 병합 알고리즘은 구현이 복잡할 수 있음.
  2. 균형 유지 어려움
    • 데이터 분포에 따라 트리의 균형을 유지하는 것이 어려울 수 있음.

그냥 지리 탐색에 좋다는 점만 알면 될듯

728x90