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

• 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)

2. 첫 번째 포인트 (1,1) 을 삽입함. 새로운 리프 노드가 생성되고 (1,1)이 포함됨.

Root
 └── (1,1)

3. 두 번째 포인트 (3,2) 를 삽입함. 현재 리프 노드의 경계 상자가 갱신됨.

Root
 └── (1,1), (3,2)

4. 세 번째 포인트 (6,3) 을 삽입함. 리프 노드가 가득 찼으므로, 분할 연산이 발생함.

Root
 ├── (1,1), (3,2)
 └── (6,3)

5. 나머지 포인트들을 차례대로 삽입함. 리프 노드가 가득 차면 분할 연산이 발생하며, 상위 노드의 경계 상자가 갱신됨.

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)

3. 각 리프 노드에서 검색 범위와 겹치는 포인트를 찾음.

Result: (3,2), (6,3)

장단점

장점

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

단점

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

---

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