Geospatial data and B-Tree

https://github.com/POODADAK/poodadak-client

팀프로젝트를 진행하면서 사용자의 위치정보(위도, 경도)기반으로 주변에 있는 화장실을 찾아주는 기능을 개발해야할 일이 있었다.

그런데 위치정보라는 것은 일반적인 데이터가 아니기 때문에 DB 에서 검색을 할때 "특정 위도/경도 포인트의 주변 500m 내의 존재하는 위도/경도 포인트들" 을 어떻게 가져와야 할지 고민을 했었다.

조금 조사를 해봤더니 몽고DB 에서는 기본적으로 Geospatial 데이터타입과 2dsphere 인덱싱을 지원해서 관련된 쿼리또한 네이티브로 지원해서 편하게 기능 구현을 할 수 있었다. https://www.mongodb.com/docs/manual/geospatial-queries/   

Geospatial Queries — MongoDB Manual

기능구현자체는 몽고에서 지원하는 기능을써서 쉽게 해결했지만. 이런 위치기반 정보가 DB 에서 어떻게 동작하는지 많이 궁금했다. 

1. 위도/경도 데이터의 인덱싱(2dsphere 인덱싱)은 어떻게 이루어지는가?

특정 지형데이터를 GEOJSON 포멧에 맞추어 몽고 DB 에 넣으면 몽고 DB는 구글 오픈소스 S2 패키지를 이용해서 해당지형을 최소한의 셀(500m~100km 사이즈 사이)로 덮고 해당 셀들을 B-Tree에 넣어서 관리한다고 한다.

2dsphere가아닌 기존의 레거시 2dindex에서는 인덱스를 지정할때 특정 지역을 4분면으로 나누어 각각의 위치를 2비트로 인덱싱 하는 과정을 재귀적으로 거친다고 공식문서에 설명이 되어있다. 예를 들어 아래와 같이 

특정 지형을 00, 01, 10, 11의 4분면으로 나눈뒤 각각의 4분면에서 또 4분면으로 나누는것. 가장 오른쪽 하단의 11을 재귀적으로 나누면서 인덱싱한다면  특정 지역은 11 11 11 과 같은 prefix를 가진채로 인덱싱 되기때문에 빠르게 찾을 수 있다고 한다. 

아마도 2dsphere 인덱스 에서도 이와 비슷한과정을 B-Tree로 구현한게 아닌가 싶다. 

2. 그런데 B-Tree가 무엇일까?

B-Tree를 이해하기 위해서는 대략적인 디스크 구조 부터 이해하는 것이 좋다.  

일반적으로 하드디스크의 구조는 원반과 그 원반의 데이터를 읽어들이는 바늘로 구성되어있는데 

갓갓 Abdul Bari 선생님의 도식. Abdul Bari 선생님은 정말 어려운 주제를 너무 차근차근 단계적으로 잘설명해주신다...

RAM보다 하드디스크에서 정보를 읽어 들이는 속도가 더 느리기 때문에 저 디스크위에서 바늘이 움직이는 거리를 최소화하는 것이 속도향상에 중요한 요소이다. 

디스크위에서 섹터(원을 피자처럼 구분한 부분)와 트랙(각각의 원)이 겹치는 부분을 "블록"으로 부르며 구분하는데 DBMS 에서는 해당 블록의 가용용량에따라서 차근차근 데이터를 저장해 나간다. 즉 하드드라이브에서는 블록을 단위로 데이터에 접근할 수 있다고 생각 할 수 있을 것이다( === 탐색하는 블록의 갯수가 줄어들수록 속도가 빨라지는것).

예를들어 블록의 크기가 512bytes 이고 DB의 레코드 하나의 크기가 128bytes 라면  1개의 블록에는 총 4개의 레코드가 담길 수 있다. 만약 DB에 그런 레코드가 100개 라면 모든데이터를 저장하기위해 총 25개의 블록이 필요하다.

만약 레코드가 1000개라면 특정 레코드를 저장하기위해 250개의 블록이 필요할테고 레코드를 탐색해야할때는 최악의 경우 250개의 블록을 선형으로 전부 탐색해야 할 것이다. 

250개의 블록을 전부 탐색하지 않고 더 빠르게 탐색하는 방법은 없을까?

여기서 필요한게 인덱싱이다.

각각 레코드의 포인터(하드드라이브 상의 위치주소)만을 지닌 인덱스를 생성해서 관리한다고 가정해보자. 인덱스에는 실제 데이터가 담긴 레코드와 달리 최소한의 정보(포인터와 id 정도)만 담기기 때문에 더 적은용량을 차지 할 것이다.  인덱스 레코드 1개의 용량이 16bytes 라면 1000개의 index를 전부 저장하는데 약 33...개의 블록이 필요할 것이다. 

즉 최악의 경우 250개보다 더적은 33 + 1의 블록을 탐색하는 것으로 원하는 데이터를 찾을 수 있다. (+ 1은 모든 인덱스를 탐색후 실제 데이터가 담긴 블록을 읽기 때문에 추가 한것).

만약 이 인덱스데이터 조차 엄청 커지기 시작한다면 어떻게 할까?

이때 등장하는 것이 멀티레벨 인덱싱이다. 

즉 인덱스에 대한 인덱스를 추가로 만들어서 탐색해야하는 디스크 블록의 숫자를 줄여나가는 것이다.

이러한 멀티레벨 인덱스 데이터들을 표현하기에 적합한 자료구조는 m-way tree이다.

이진탐색트리와 비슷하지만 노드의 키값이 원하는 만큼(이래서 이름이 m-way) 존재하고 노드의 child 노드는 parent노드의 키 갯수 +1 개 만큼 존재 할 수 있는 트리 구조다.

다만 m-way트리의 경우 개념적으로 이렇다할 제약이 없기 때문에 최악의 경우 tree의 height가 o(n)으로 늘어날수 있다. tree height가 o(n)일경우 선형적으로 모든 블록을 탐색하는것과 다름이 없기 때문에 개선이 필요하다. 

한개를 삽입할때 마다 층이 1개가 높아지는 m-way트리...

b Tree가 그런 m-way트리의 한계를 개선하기 위해 아래와 같은 제약을 둔 트리로 생각하면 된다. 

1. 모든 노드는 적어도 m/2 만큼 노드를 채워야한다.
2. 단 루트노드는 1번의 제약을 적용하지 않는다 (루트노드는 키값이 1개만 있어도 괜찮다)
3. 모든 리프노드는 똑같은 height에서 존재해야한다. 

위의 제약을 모두 만족 하는 B Tree를 만들 경우 리프 노드가 모두 같은 레벨에 존재하는것이 보장 되기 때문에 삽입 삭제 탐색 모두 O(logn) 시간복잡도를 지닐 수 있다. 

3. 지구는 둥글기 때문에 2개의 포인트(위도/경도) 사이의 거리를 구할때 피타고라스 정리를 사용해서는 정확한 거리를 구하지 못할것텐데 이부분은 어떻게 해결 되는 건가? 

이 부분은 생각보다 간단했는데 지구상의 두 위치좌표간의 거리를 구하는 것은 haversine 이라는 수학 공식이 이미 존재했었다. 잘 알려진 공식이라서 NPM 패키지도 존재했고... 

https://www.npmjs.com/package/haversine-distance

haversine-distance

Reference

https://en.wikipedia.org/wiki/Spatial_database

Spatial database - Wikipedia

http://s2geometry.io/

S2 Geometry

https://www.mongodb.com/blog/post/new-geo-features-in-mongodb-24

New Geo Features in MongoDB 2.4 | MongoDB Blog

https://www.geeksforgeeks.org/introduction-of-b-tree-2/

Introduction of B-Tree - GeeksforGeeks

https://www.youtube.com/watch?v=aZjYr87r1b8&ab_channel=AbdulBari