R-tree

R-tree

개요

• B+ 트리는 1차원 데이터(컴포넌트의 갯수가 한 개인 경우 / 나이). 2차원이 넘어가게 되면(컴포넌트의 갯수가 여러개인 경우 / 위치정보, 3D 데이터) B+트리는 동작을 하지 못하게 된다.
• B 트리 패밀리라고 해서 최초에 B+ 트리가 만들어지고 그 이외에 B 트리, B* 트리, B# 트리 등 여러가지가 만들어졌다.
• 하지만 대부분의 DBMS는 B+ 트리를 구현해 놓고 있다. 왜냐하면 B+트리가 자료구조가 간단하기 때문.
• 다차원 데이터를 색인하고 검색하는데는 R 트리를 사용
• R 트리도 마찬가지로 R 트리, R+ 트리, R* 트리, R# 트리 등이 있다. 이것들을 전부 R 트리 패밀리라고 부른다.
• DBMS에는 주로 R* 트리로 구현되어 있다. 성능이 좋기 때문

R-tree

• Guttman이라는 사람이 만듬
• R트리는 CAD나 GIS 애플리케이션에서 스페셜한 데이터(크기를 가지고 있는 오브젝트)를 효율적으로 다루기 위한 색인 기법
• B+트리는 다차원 공간 탐색에 적합하지 않다. 왜냐하면 콤퍼넌트의 갯수가 하나기 때문에 쓸 수가 없다. 따라서 R 트리를 개발
• exact matching(조건이 =인 경우. 나이가 20인 사람을 찾아주시오 이런거)에는 해시 테이블, 즉 해싱이 좋다. 단번에 그 값을 찾을 수 있기 때문에. 하지만 range search(나이가 19보다 크거나 같고 23보다 작은 사람을 찾아주시오 같은거)에는 해싱을 쓸 수가 없다. 범위 탐색에는 그만큼 해싱 탐색을 돌려야 되므로 몹시 비효율적이다. 따라서 R 트리를 개발
• B트리처럼 1차원의 키 값을 정렬할 수 있는 구조는 다차원의 경우에는 동작하지 않는다. 1차원의 경우에는 정렬을 할 수 있지만(정렬을 할 수 있는 경우에는 데이터의 처리가 쉽다), 다차원의 경우에는 어느 컴포넌트를 기준으로 정렬을 해야 할지 알 수가 없다. 따라서 R트리를 개발

R-tree의 구조

• 여기서는 2차원 데이터. 까만색을 주유소라고 가정. 주유소들이 그루핑이 되어있다. 속에도 그루핑이 되어있고 바깥에도 그루핑이 되어있다. 공간적으로 그루핑이 되어 있다. 색인 구조가 다 이렇다. 지난 B 트리 같은 경우도 해당 키 값보다 크거나 같은 것은 오른쪽으로, 작은것은 왼쪽으로 그루핑이 되어 있었다. 그루핑을 해야 탐색에서 효율적이다. 그루핑을 하게 되면 검색 범위를 굉장히 좁힐 수가 있다.
• 한 지점을 찍고 해당 지점에서 반경 1km 내에 있는 주유소를 찾아주시오라고 할 수 있다. 그러면 나랑 겹치는 노드가 있는 곳으로 따라 내려가면 된다. 그렇게 하기 위해 데이터를 그루핑 해 놓는 것. 이것이 색인구조이다.

R-tree Index Structure

• B 트리하고 똑같다. 차이가 있다면 1차원이 아니라 다차원이라는 것. 따라서 순서를 매길 수 없다는 점. 정렬을 할 수 없다는 점
• R 트리는 B 트리와 비슷하게 높이 균형 트리이다.
• leaf 노드는 실제 데이터 오브젝트에 대한 포인터를 가지고 있다. 즉 leaf 노드에 있는 마지막 포인터가 데이터가 어디에 들어있는지를 가리킨다. 실제 DB 시스템에서 데이터는 데이터 파일로 저장이 되고 인덱스는 인덱스 파일로 저장이 된다.
• 노드들은 64kb, 또는 32kb로 구현이 된다.
• 인덱스는 완전한 dynamic이다.
  • dynamic 구조는 언제든지 업데이트(삽입, 삭제, 갱신)를 할 수 있는 구조. 업데이트를 하고자 할 때 몇 개의 노드에만 영향을 미친다. 따라서 사용자가 데이터를 검색하고 있는 동안에도 실제 데이터 파일이나 색인 구조를 업데이트를 할 수 있는 것이 dynamic 구조. 몇 개의 노드만 건드리기 때문.
  • static 구조는 전체 데이터의 통계적인 정보를 이용해서 색인 구조를 만든다. 따라서 몹시 효율적이다. 하지만 전체 데이터의 통계적인 정보를 이용해야 되니까 내가 데이터를 업데이트 하고 있는 동안에 누군가가 검색을 할 수 없게 된다. 따라서 static 구조의 경우는 심야에 사람들의 접근을 차단하고 시스템을 업데이트한다.
• Leaf node entry
  • entry는 (key-value, pointer)의 쌍을 의미한다.
  • R트리에서는 (I, tuple-id)로 구성된다. tuple-id는 B트리에서의 포인터를 의미한다.
  • 그리고 R트리는 n차원이니까 key 값인 I는 $I$ = ($I_0$, … , $I_{n-1}$) 까지 n개가 들어가게 된다.
• Nonleaf node entry
  • 이것도 마찬가지로 (I, child-pointer)로 구성된다.
  • I는 n개의 키값을 가지고 있다.

R-tree Properties

• 성격도 역시 B 트리하고 똑같다.
• M : fanout. 한 노드가 가질 수 있는 최대 엔트리 갯수
• m : 한 노드에 들어가는 최소 엔트리 갯수. m은 M/2이상이어야 한다.
• B트리와의 차이점은 키 값이 MBR(minimum bounding rectangle)을 가지고 있다. B트리는 다이렉트 키 값이 들어있지만 R트리의 키 값은 특정 오브젝트를 감싸는 최소 바운딩 사각형의 꼭지점 중 두 개의 좌표가 들어가게 된다. 왜냐하면 특정 오브젝트를 그대로 집어넣기는 어렵기 때문에. 별 모양의 오브젝트라고 가정해보면 해당 모양을 그대로 집어넣긴 어렵다. 따라서 해당 모양을 사각형으로 감싸서 집어넣는 것.
  • 3차원 데이터라면 육면체의 꼭지점 중 두 개의 좌표. 이렇게 두 개의 점으로 오브젝트를 간소화.
• R 트리의 높이는 $⎡log_mN⎤$보다 작거나 같다. 이것도 중요한 특징. 여기서 m은 한 노드에 들어가는 최소 엔트리 갯수이고, N은 R트리의 인덱스 레코드의 갯수. 즉 실제 데이터의 갯수.
  • 엄청나게 많은 데이터를 m을 베이스로 log를 취하므로 실제 서치하는 데이터의 갯수를 엄청 줄일 수 있다. 이렇게 금방 찾을 수 있다. R트리의 높이는 실제 검색하는 데이터의 갯수라고 보면 된다.
• 나머지는 B트리와 성격이 같다.

Range Searching

• 내가 현재 있는 위치에서 반경 1km 내에 있는 주유소를 찾아주시오라고 쿼리를 날림
• 해당 반경의 원과 겹치는 노드는 모두 검색
• 처음에 루트로 들어간다. 루트 밑에 1번 2번 3번 노드가 있다. 1, 2, 3노드 모두 해당 반경과 겹치므로 셋 중에서 가장 가까운 노드부터 먼저 검색
• 2번 속에 있기 때문에 2번이 제일 가까우므로 2번부터 간다. 2번 노드 아래의 7, 8, 9 중에 8번이 제일 가까우므로 8번 방문
• 8번은 leaf 노드로 실제 데이터가 들어있다. 그럼 실제 데이터 중 해당 반경과 겹치는 데이터를 찾는다. 2개의 데이터를 찾을 수 있다.
• 그 다음 가까운 노드를 방문. 7번을 방문한다. 방문해서 겹치는 데이터를 찾는다. 2개의 데이터를 찾을 수 있다.
• 그 다음 나머지 9번을 방문한다. 방문해서 겹치는 데이터를 찾는다. 1개의 데이터를 찾을 수 있다.
• 그 다음에 1번 노드로 내려간다. 하지만 1번 노드에는 4, 5, 6번 중에 해당 반경과 겹치는 노드가 없다. 따라서 해당 노드들은 방문할 필요가 없다.
• 그 다음으로 3번 노드로 내려간다. 마찬가지로 3번 노드의 10, 11, 12번도 해당 반경과 겹치는 노드가 없으므로 방문할 필요가 없다.
• 따라서 지금까지 찾은 5개의 데이터가 찾고자 하는 데이터이다.
• 실제 알고리즘은 다음과 같다.
  • 처음에 해당 노드가 leaf인지 non leaf인지 검사를 한다. 해당 노드가 leaf이면 실제 데이터를 가지고 있으므로 실제 데이터를 읽어보면 된다.
  • 하지만 non leaf이면 오버랩 되는 노드가 어떤 것인지를 체크해서 겹치는 노드는 모두 따라 내려가봐야 한다. 만약 오버랩되는 엔트라가 있으면 해당 엔트리를 root로 해서 다시 서치 함수를 호출한다.(재귀) 그렇게 leaf까지 도달해서 겹치는 데이터가 있는지를 검색해봐야 한다.

Insertion

• B트리하고 같다.

• 유일한 차이점은…

  • B트리는 데이터를 분할하는 것이 굉장히 쉽다.
  • 예를 들어 overflow가 생기면 기존 데이터가 정렬되어 있으니까 그냥 반으로 나눌 수 있다.
  • 하지만 R트리 같은 경우는 다차원 데이터니까 자르기가 굉장히 어렵다. 순서가 없으니 가운데가 없어 어떻게 잘라야 할 지 알 수가 없다.

• 데이터 엔트리 E를 R트리에 집어넣고자 한다.

• 먼저 자리를 찾는다 (ChooseLeaf 함수)

• 자리가 있으면 집어넣으면 되고 자리가 없으면 SplitNode함수를 호출해서 데이터를 양분한다.

• 데이터가 양분되었으면 새로운 노드가 들어왔으므로 새로운 노드가 들어왔다는 것을 parent 노드에 알려야 하므로 AdjustTree함수를 호출한다.

• 이렇게 하다보면 루트까지 쪼개질 수도 있다.

• 전체적인 알고리즘은 B트리하고 똑같지만 유일한 차이점은 SplitNode. 데이터를 어떻게 나눌 것인가.

• ChooseLeaf 함수는…

  

  • 내가 데이터를 삽입하고 싶은데 내가 들어갈 자리를 찾는 것.
  • 만약 위에서 3번에 새로운 주유소가 생겼다고 가정해보자. 그러면 해당 위치와 가장 가까운 곳에 해당 데이터를 집어넣어야 할 것이다.
  • 가장 인접한 노드들 중에서 해당 노드를 최소 한도로 확장 시켜서 해당 데이터를 커버할 수 있는 곳에 집어넣어야 한다.즉 10, 11, 12번 사각형들을 최소로 확장해서 해당 데이터를 커버할 수 있는 사각형(노드)에 집어넣어야 한다. 이것이 핵심.
  • 루트부터 내려가서 leaf가 아니면 해당 데이터를 포함할 때 박스를 최소한으로 확장시킬 수 있는 non leaf노드를 찾고, leaf까지 왔으면 leaf 중에서도 최소한으로 확장시킬 수 있는 곳을 찾는다.

• AdjustTree는…

  • 데이터를 집어넣었다. 집어넣었는데 해당 데이터를 포함시킬 박스가 overflow가 생겨 새로운 노드를 만들어야 한다면, 새로운 노드를 가리키는 포인트와 키 값을 parent한테 받아야 한다. 이 과정을 밑에서부터 위로 진행해 나간다.
  • 이것도 전체적인 알고리즘은 B트리하고 같다. 차이점은 키 값이 B트리에서는 그냥 일차원 데이터였지만 R트리에서는 box라는 것.
  • 위에 있는 parent 노드의 키 값이 밑에 있는 값들의 카테고리를 결정. 해당 값보다 작은 것은 왼쪽, 같거나 큰 것은 오른쪽. 이렇게 카테고리를 결정해놔야 데이터를 찾을 때 불필요한 부분을 잘라낼 수 있다.
  • B트리의 경우에는 1차원 데이터니까 키 값이 하나만 있으면 되는데 R트리는 키 값이 차원의 갯수만큼 필요하다. 이러한 차이가 존재.

• Deletion은…

  • 삭제하고자 하는 데이터가 어디에 있는지를 찾아야한다. 따라서 Findleaf를 통해 해당 데이터를 찾고 데이터를 삭제.
  • 만약 삭제를 했는데 데이터의 갯수가 fanout의 절반보다 작아지게 되면, B트리는 1차원 데이터니까 순서를 가지고 있으므로 이웃한 노드를 살펴봐서 두 개를 합칠 수 있으면 합친다. 하지만, R트리는 순서가 없어서 합치기가 굉장히 어렵다. 따리서 절반 이하로 떨어지게 되면 그 노드를 삭제시켜버리고 그 노드에 들어있는 데이터를 새로 채우는 재삽입을 한다. 이것이 CondenseTree함수.

• FindLeaf는…

  • 내가 들어갈 자리를 찾는 것.
  • 재귀함수이다. 해당 엔트리를 찾을 때 까지 FindLeaf를 재귀호출하면서 밑으로 파고 내려간다.

• Node Splitting

  

  • R트리의 핵심. overflow가 발생했을 때 어떻게 노드를 나눌 것인가.

  • 최초의 R트리의 Node Splitting 알고리즘은, 데이터를 양쪽으로 나누고 난 다음에 두개를 커버하는 박스의 전체 에리어가 최소화되도록 하고자 하는 것이 목적이다.

  • 그루핑을 잘못하게 되면 찾고자 하는 쿼리에(ex. 해당 위치에서 반경 1km 내의 주유소를 찾아주시오) 해당하는 데이터가 없음에도 불구하고 오버랩되는 노드가 발생해서 필요치 않는 방문을 해야되게 될 수 도 있다.

  • 1차원 데이터는 순서가 있기 때문에 자르기가 쉽지만 다차원 데이터는 순서가 없으므로 자르기가 매우 어렵다.

  • 그래서 R트리 저자가 두 개의 알고리즘을 제시

    • Exhaustive Algorithm

      • 모든 경우를 다 조사해보는 것. 어떻게 데이터를 양부하는 것이 제일 좋은지를 모두 다 조사해 보는 것.
      • $2^{M-1}$개까지. M은 fanout의 갯수
      • 당연히 시간이 너무 많이 걸러셔 사용하지 않음

    • Quadratic-Cost Algorithm

      • 빅오가 $M^2$ (M : fanout. 한 노드가 포함할 수 있는 최대의 데이터 갯수)
      • 전체 데이터의 갯수가 M + 1개.
      • 두 개의 그룹으로 나누기 위해 시드를 두 개 뽑는다. (PeekSeeds)
        • 만약에 두 개의 시드가 같은 그룹에 들어갔을 경우에 두 개를 포함하는 박스의 면적이 가장 커지는 것을 시드로 정한다.
        • 즉 가장 멀리 있는 데이터를 시드로 뽑는다.
      • 이 두 개의 시드가 두 개의 그룹의 대장이 되는 것
      • 남아있는 데이터는 하나하나씩 뽑아서 두 개의 그룹 중에서 어디에 집어넣을 것인지를 체크
      • 여기서 어떤 데이터를 먼저 뽑아서 검사하느냐도 전체 시스템의 성능에 영향을 많이 준다.
        • 양쪽 그룹에 들어갔을 때 그 박스의 크기 차이가 가장 큰 것을 먼저 선택한다.
        • $d_1$을 해당 데이터가 그룹 1에 들어갔을때의 면적, $d_2$가 그룹 2에 들어갔을때의 면적이라고 했을 때 $d_1$과 $d_2$의 차이가 가장 큰 것이 그 다음에 검사할 데이터로 선정된다.
        • 역시 남아 있는 데이터를 대상으로도 같은 과정을 반복한다. 이를 통해 어떤 데이터를 그 다음으로 선정할 것인지를 정한다. (PeekNext)
      • PeekNext를 통해 데이터를 선정해서 확장이 가장 작게 일어나는 그룹에 해당 데이터를 집어넣는다.

    • Linear-Cost Algorithm

      • 빅오가 $M$ (M : fanout)

      • PeekNext는 그냥 랜덤으로 선정한다.

      • LinearPeekSeed는 각 차원마다 제일 멀리 있는 두 개를 찾는다.

        

        • $x$축의 관점에서 제일 멀리 있는 두 개를 찾는다. 이것이 후보 1.
        • 또 $y$축의 관점에서 제일 멀리 있는 두 개를 찾는다. 이것이 후보 2.
        • 이 후보 2개 중 더 멀리 있는 것를 시드로 정한다.
        • 데이터의 크기를 정규화해서 (각 데이터의 거리)/(전체 데이터의 크기) 각 차원별로 계산해 가장 큰 값을 가지는 것을 후보로 삼는다.
        • 그 후보들 중에서 가장 큰 값을 가지는 것을 시드로 정한다.

    • Performance

      

      • 가로축은 데이터의 갯수, 세로축은 삽입 삭제되는 속도

      • 삽입 삭제할때 Quadratic Cost가 시간이 더 많이 걸리는 것을 알 수 있다.

        

      • 가로축은 데이터의 갯수, 세로축은 탐색할 때 디스크를 몇 번 액세스하는지

      • Quadratic이나 Linear나 속도가 비슷하다.

        

      • 가로축은 데이터의 갯수, 세로축은 속도.

      • 비슷하다.

        

      • 실제 데이터를 R트리로 저장할 때 어느정도 공간을 차지하는지.

      • Linear Cost가 오히려 공간이 더 많이 든다는 것을 알 수 있다.

    • Conclusion

      • 결론적으로 non-zero size의 데이터 오브젝트를 색인하는 데 R트리가 굉장히 효율적이다.
      • Linear Cost 알고리즘과 Quadratic Cost 알고리즘을 비교해 봤을 때 Linear Cost 알고리즘이 더 비싼 기술인 만큼 더 좋다고 판단.