T-트리
T-tree |
컴퓨터 공학에서 T 트리는 Datablitz, eXtremeDB, MySQL Cluster, Oracle TimesTen, MobileLite와 같은 메인 메모리 데이터베이스에서 사용되는 바이너리 트리 데이터 구조의 한 유형이다.
T트리는 B트리가 하드디스크와 같은 블록 지향 2차 저장장치의 저장에 최적화된 인덱스 구조인 것처럼 인덱스와 실제 데이터가 모두 메모리에 완전히 저장되는 경우에 최적화된 균형 인덱스 트리 데이터 구조다.T-tree는 AVL 트리와 같은 메모리 내 트리 구조의 성능 이점을 얻는 동시에 그들에게 공통적인 대용량 저장 공간 오버헤드를 회피한다.
T-tree는 인덱스된 데이터 필드의 복사본을 인덱스 트리 노드 자체에 보관하지 않는다.대신 실제 데이터가 항상 인덱스와 함께 메인 메모리에 있다는 점을 이용해 실제 데이터 필드에 대한 포인터만 담는다.
T-트리의 'T'는 이 유형의 지수를 처음 설명한 원본 논문에서 노드 데이터 구조의 모양을 가리킨다.[1]
노드 구조
T-트리 노드는 일반적으로 상위 노드, 왼쪽 및 오른쪽 하위 노드, 순서 배열의 데이터 포인터 및 일부 추가 제어 데이터로 구성된다.두 개의 하위 트리가 있는 노드를 내부 노드라고 하고, 하위 트리가 없는 노드를 리프 노드라고 하며, 하위 트리가 하나만 있는 노드를 하프 리프 노드라고 한다.값이 노드의 현재 최소값과 최대값 사이에 있는 경우, 노드를 값의 경계 노드라고 한다.
각 내부 노드에 대해 가장 작은 데이터 값(가장 큰 하한이라고 함)의 이전 버전과 가장 큰 데이터 값의 후속 버전(최소 상한이라고 함)을 포함하는 리프 또는 하프 리프 노드가 존재한다.리프 및 하프 리프 노드에는 데이터 배열의 최대 크기부터 최대 크기까지의 데이터 요소가 얼마든지 포함될 수 있다.미리 정의된 최소 요소 수와 최대 요소 수 사이에서 내부 노드 점유 유지
알고리즘
검색
- 루트 노드에서 검색 시작
- 현재 노드가 검색 값의 경계 노드인 경우 해당 데이터 어레이를 검색하십시오.데이터 배열에서 값을 찾을 수 없는 경우 검색이 실패함
- 검색 값이 현재 노드의 최소값보다 작으면 왼쪽 하위 트리에서 검색을 계속하십시오.왼쪽 하위 트리가 없으면 검색이 실패함
- 검색 값이 현재 노드의 최대값보다 크면 오른쪽 하위 트리에서 검색을 계속하십시오.올바른 하위 트리가 없는 경우 검색이 실패함
삽입
- 새 값에 대한 경계 노드를 검색하십시오.이러한 노드가 있는 경우:
- 데이터 배열의 공간이 남아 있는지 확인한 다음, 있다면 새 값을 삽입하고 마침표를 작성하십시오.
- 사용 가능한 공간이 없는 경우 노드의 데이터 배열에서 최소값을 제거하고 새 값을 삽입하십시오.이제 새 값이 삽입된 노드에 대해 가장 큰 하한을 가진 노드로 진행하십시오.제거된 최소값이 여전히 여기에 적합한 경우 노드의 새 최대값으로 추가하거나, 그렇지 않으면 이 노드에 대해 새 오른쪽 하위 노드를 생성하십시오.
- 경계 노드를 찾을 수 없는 경우 값을 검색한 마지막 노드에 삽입하십시오.이 경우 새로운 값은 새로운 최소값 또는 최대값이 된다.값이 더 이상 맞지 않으면 새 왼쪽 또는 오른쪽 하위 트리를 생성하십시오.
새 노드를 추가한 경우 아래 설명된 대로 트리를 재조정해야 할 수 있다.
삭제
- 삭제할 값의 경계 노드를 검색하십시오.경계 노드를 찾을 수 없으면 완료하십시오.
- 바인딩 노드에 값이 없으면 완료하십시오.
- 노드의 데이터 배열에서 값을 삭제하십시오.
이제 노드 유형별로 구분해야 한다.
- 내부 노드:
노드의 데이터 어레이가 이제 최소 요소 수보다 작으면 이 노드의 가장 큰 하한 값을 데이터 값으로 이동하십시오.값이 제거된 하프 리프 또는 리프 노드에 대해 다음 두 단계 중 하나를 계속 진행하십시오.
- 리프 노드:
데이터 배열의 유일한 요소인 경우 노드를 삭제하십시오.필요한 경우 트리의 균형을 재조정하십시오.
- 하프 리프 노드:
노드의 데이터 어레이를 오버플로우 없이 리프 데이터 어레이와 병합할 수 있는 경우 그렇게 하고 리프 노드를 제거하십시오.필요한 경우 트리의 균형을 재조정하십시오.
회전 및 균형 조정
T 트리는 기본 자체 균형 이진 검색 트리 위에 구현된다.구체적으로, 리먼과 캐리의 기사는 AVL 트리처럼 균형 잡힌 T 트리를 묘사하고 있다: 노드의 자식 트리가 적어도 두 단계씩 높이가 다를 때 그것은 균형을 잃게 된다.이는 노드를 삽입하거나 삭제한 후에 발생할 수 있다.삽입 또는 삭제 후 트리는 잎에서 루트까지 스캔된다.불균형이 발견되면 나무 한 그루 회전이나 한 쌍의 회전이 이뤄져 나무 전체의 균형이 보장된다.
회전으로 인해 내부 노드가 최소 항목 수보다 적으면, 노드의 새로운 하위 항목(렌)이 내부 노드로 이동한다.
성능 및 스토리지
한때 성능상의 이점 때문에 메인 메모리 데이터베이스에 T-tree가 널리 사용되었지만, 최근 대형 메인 메모리 데이터베이스의 경향은 프로비저닝 비용에 더 중점을 두고 있다.현대의 NOSQL 데이터베이스 시스템은 종종 수조 개의 레코드를 저장하기 때문에, 실제 값을 포함하는 단일 인덱스라도 저장하는 메모리 비용은 수십, 심지어 수백 테라바이트를 초과할 수 있다.
참고 항목
다른 나무들
참조
- ^ Lehman, Tobin J.; Carey, Michael J. (25–28 August 1986). A Study of Index Structures for Main Memory Database Management Systems. Twelfth International Conference on Very Large Databases (VLDB 1986). Kyoto. ISBN 0-934613-18-4.
