B-트리x

컴퓨터 과학에서 B^x 트리는 기본적으로 움직이는 물체의 효율적인 B+ 트리 기반 인덱스 구조를 업데이트하는 데 사용되는 쿼리다.

지수 구조

B-트리의^x 기본 구조는 내부 노드가 디렉토리의 역할을 하는 B+ 트리로, 각각 오른쪽 형제자매에 대한 포인터를 포함하고 있다.이전 버전의 B-트리에서는^x 나뭇잎 노드가 인덱싱되고 있는 이동 객체 위치와 해당 인덱스 시간을 포함했다.^[1]최적화된 버전에서 각 리프 노드 항목은 개체의 ID, 속도, 단차원 매핑 값 및 최신 업데이트 시간을 포함한다.^[2]이동 물체의 위치를 저장하지 않음으로써 팬아웃이 증가하는데, 이는 매핑 값에서 도출될 수 있기 때문이다.

이동 객체에 B+ 트리 활용

다른 많은 이동 객체 인덱스에 대해서는, 2차원 이동 객체를 O = (x, y), (vx, vy), t "로 선형 함수로 모델링하며, 여기서 (x, y), (vx, vy)는 주어진 시간 인스턴스 t, 즉 마지막 업데이트 시간에서 객체의 위치와 속도다.B+ 트리는 단차원 데이터를 인덱싱하는 구조다.B+ 트리를 움직이는 물체 지수로 채택하기 위해 B-트리는^x 시간 t에 있는 물체의 위치를 단차원 값으로 통합하는 선형화 기법을 사용한다.특히 객체는 업데이트 시간에 따라 먼저 분할된다.동일한 파티션 내의 개체의 경우 B-트리는^x 선형 보간법으로 추정된 특정 시간에 위치를 저장한다.그렇게 함으로써 B-트리는^x 객체의 업데이트 시간을 저장하지 않고 동일한 파티션 내의 모든 객체를 일관성 있게 볼 수 있게 한다.

둘째, 공간은 격자로 분할되고, 물체의 위치는 공간충전 곡선(예: Peano 또는 Hilbert 곡선)에 따라 분할 영역 내에서 선형화된다.

마지막으로 파티션 번호(시간 정보)와 선형 순서(위치 정보)의 조합으로 B-트리(B-tree^x)에서 객체가 1차원 인덱스 키 Bvalue^x:

${\displaystyle B^{x}value\left(O,t\right)=\left[indexpartition\right]_{2}+\left[xrep\right]_{2}}$

여기서 인덱스 파티션은 업데이트 시간에 의해 결정되는 인덱스 파티션이며 ${\displaystyle {\mathrm{xrep}}_{}}$은 ${\displaystyle {\mathrm{}}_{}}$ 시간에 개체 위치의 공간 채우기 곡선 값이며,${\displaystyle {}_{}}$[ X ${\displaystyle {]}_{}}$ 2 ${\$2}}은 x의 이진값을 나타내며$$, "+"는 결합을 의미한다.

O (7, 2), (-0.1,0.05), 10), tmu = 120, O에 대한 B값을^x 다음과 같이 계산할 수 있다.

1. 언급한 바와 같이 O는 파티션 0에서 색인화된다.따라서 인덱스파티션 = (00).₂
2. 파티션 0의 라벨 타임스탬프에서 O의 위치는 (1,5)이다.
3. 순서 = 3과 함께 Z-곡선을 사용하면 O의 Z-값, 즉 xrep은 (010011)이다.₂
4. 인덱스 파티션 및 xrep 연결, Bvalue^x (00010011)=₂19.
5. 예 O ( (0,6), (0.2, -0.3 )),10) 및 tmu=120의 파티션 레이블 타임스탬프에서 O의 위치: ??

삽입, 업데이트 및 삭제

새 객체가 주어지면 인덱스 키가 계산된 다음 B+ 트리에서와 같이 객체를 B-트리에^x 삽입한다.업데이트는 삭제 후 삽입으로 구성된다.키를 검색하여 객체를 삭제할 수 있도록 각 인덱스의 최신 키를 보관하는 보조 구조를 채용한다.인덱싱 키는 트리에 영향을 미치기 전에 계산된다.이러한 방식으로 B-트리는^x B+ 트리의 좋은 속성을 직접 계승하고, 효율적인 업데이트 성능을 달성한다.

쿼리

범위 조회

범위 쿼리는 직사각형 범위 $q{\displaystyle }$=${\displaystyle }$(${\displaystyle }$[ ${\displaystyle q}$ x ${\displaystyle 1}$,${\displaystyle q}$ ${\displaystyle y}$ ${\displaystyle 1];}$ [${\displaystyle q}$ ${\displaystyle x}$ ${\displaystyle 2;}$ ${\displaystyle q}$ ${\displaystyle \mathrm{y}}$ ${\displaystyle ]}$) ${\$])에 속하는 모든 객체를 검색한다$.$$\left[qx2;qy2\right]\right}$ 현재$$ 시간 이전이 아닌 시간 t ${\displaystyle q}$ ${\displaystyle tq}.$

B 트리는^x 질의 응답에 질의 창 확대 기법을 사용한다.B-트리는^x 업데이트 시간 이후 어느 시점부터 물체의 위치를 저장하기 때문에, 확대는 두 가지 경우를 포함한다. 즉, 위치를 더 이른 시간으로 되돌리거나 더 늦은 시간으로 전환해야 한다.주요 아이디어는 쿼리 창을 확대하여 해당 레이블 타임스탬프에서 쿼리 창 내에 위치하지 않고 쿼리 타임스탬프에서 쿼리 창으로 들어가는 모든 개체를 둘러싸도록 하는 것이다.

확대 후 확대된 쿼리 창에 떨어지는 물체를 찾기 위해 B-트리의^x 분할 영역을 통과해야 한다.각 파티션에서 공간 채우기 곡선의 사용은 네이티브 2차원 공간의 범위 쿼리가 변환된 1차원 공간의 범위 쿼리 집합이 된다는 것을 의미한다.^[1]

왜곡된 데이터셋의 확장 후 지나치게 큰 쿼리 영역을 방지하기 위해 쿼리 알고리즘의 최적화가 존재하며,^[3] 불필요한 쿼리 확대를 방지하여 쿼리 효율성을 향상시킨다.

K 가장 가까운 인접 쿼리

K 가장 가까운 이웃 쿼리는 k 답변이 얻어질 때까지 점진적으로 확대된 검색 영역으로 범위 쿼리를 반복적으로 수행하여 계산한다.또 다른 가능성은 iDistance 기법에 유사한 질의 아이디어를 채택하는 것이다.

기타 쿼리

범위 쿼리와 K 가장 가까운 이웃 쿼리 알고리즘을 쉽게 확장하여 간격 쿼리, 연속 쿼리 등을 지원할 수 있다.^[2]

이동 객체를 수용하도록 관계형 데이터베이스 엔진 조정

B-트리는^x B+트리 지수 위에 구축된 지수이기 때문에 삽입, 삭제, 검색 등 B-트리의^x 모든 연산은 B+트리의 연산과 동일하다.이러한 운영의 구현은 변경할 필요가 없다.유일한 차이점은 기존 DBMS에서 인덱싱 키를 저장 프로시저로 도출하는 절차를 구현하는 것이다. 따라서 B 트리는^x 커널을 건드리지 않고도 기존 DBMS에 쉽게 통합될 수 있다.

SpADE는^[4] B 트리를 사용하여^x 객체를 인덱싱하는 인기 관계형 데이터베이스 시스템 MySQL 위에 구축된 객체 관리 시스템을 이동시키고 있다.구현에서 이동 객체 데이터는 MySQL에 직접 변환되어 저장되며 쿼리는 관계형 엔진에서 효율적으로 처리되는 표준 SQL 문으로 변환된다.가장 중요한 것은 이 모든 것이 MySQL 코어에 침투하지 않고 깔끔하고 독립적으로 달성된다는 점이다.

성능 튜닝

데이터 스큐의 잠재적 문제

B^x 트리는 2차원 위치를 1차원 키로 매핑하면서 공간 분할을 위해 그리드를 사용한다.이는 왜곡된 데이터를 처리하는 동안 쿼리 및 업데이트 작업 모두에 성능 저하를 초래할 수 있다.그리드 셀이 지나치게 크면, 많은 물체가 셀에 포함된다.셀의 객체는 인덱스와 구분할 수 없기 때문에, 기본 B+ 트리에 오버플로 노드가 있을 것이다.기존의 오버플로 페이지는 트리의 균형을 파괴할 뿐만 아니라 업데이트 비용도 증가시킨다.쿼리의 경우, 주어진 쿼리 영역에 대해, 큰 셀은 더 많은 잘못된 긍정을 유발하고 처리 시간을 증가시킨다.반면에 공간이 더 미세한 격자, 즉 더 작은 셀로 분할되면 각 셀은 거의 물체를 포함하지 않는다.업데이트 비용을 최소화하기 위해 페이지 오버플로가 거의 없다.쿼리에서 잘못된 긍정이 더 적게 검색된다.그러나 더 많은 세포가 검색되어야 한다.검색된 셀의 수가 증가하면 질의의 작업량도 증가한다.

인덱스 튜닝

STB 트리는² 공간에서의 데이터 왜곡과 시간 변화에 대처하면서 B 트리의^x 성능을 조정하기 위한 자체 튜닝 프레임워크를 도입한다.공간에서의 데이터 스큐를 처리하기 위해, STB 트리는² 기준점 집합을 사용하여 전체 공간을 다른 개체 밀도의 영역으로 분할한다.각 영역은 세포 크기가 그 안의 물체 밀도에 의해 결정되는 개별 그리드를 사용한다.

B-트리에는^x 서로 다른 시간 간격에 대한 여러 개의 파티션이 있다.시간이 흐를수록 각 파티션은 번갈아 가며 커지고 축소된다.STB-트리는² 시간에 따른 데이터 변화에 적응할 수 있도록 공간 파티셔닝을 조정하기 위해 이 기능을 사용하여 인덱스를 온라인으로 조정한다.특히 파티션이 비어있는 상태로 축소되고 성장하기 시작하면서 최신 데이터 밀도에 따라 각 기준점에 대해 새로운 기준점과 새로운 그리드를 선택한다.튜닝은 주어진 시간 동안 수집된 최신 통계에 기초하여 공간 분할 방법이 최신 데이터 배포에 가장 적합하도록 한다.이를 통해 STB-트리는² 공간에서의 데이터 왜곡과 시간에 따른 데이터 변화에 따른 영향을 최소화할 수 있을 것으로 기대된다.

참고 항목

• B+나무
• 힐버트 곡선
• Z 순서(곡선)

참조