균형나무와 외부 탐색법

2-3-4 트리는 모든 중간 노드들의 자식수가 2,3,4이면서 모든 단말 노드가 같은 레벨에 있는 나무입니다.

2-3-4 나무 특징

- 2-3 나무를 확장 하여 다양한 나무를 만들수 있다.

- 데이터베이스에서 사용하는 색인구조의 형태

- 한 노드에 있을 수 있는 값의 수가 많다면 나무의 높이 감소.

- 나무의 높이가 감소하면 할수록 검색 향상됨.

2-3-4 나무의 삽입

-  단말 노드에서 이루어집니다. 삽입할 노드를 찾는동안 4-노드를 만나면 분할합니다.

2-3-4 나무의 삭제

-  먼저 삭제할 값을 포함한 노드를 찾아야 한다.

- 그 노드가 단말 노드가 아니면 그값과 그것의 중위 순위상에서 바로 앞 값을 교환함. (이 값은 항상 단말 노드에 있음)

n개의 노드로 구성된 2-3-4 나무가 있을때 나무의 높이 = 최대 logn , 탐색 시 방문하는 노드 수 최대 logn+1 이고 탐색시간 O(logn)

2-3-4 나무를 그대로 구현시 노드 구조가 복잡해지기 때문에 많은 노력이 요구되고 이진 탐색 나무보다 느려질 가능성 크다.

흑적 트리

 2-3-4 나무를 이진 탐색 나무 형태로 구현한 것이며 링크에는 흑 링크와 적 링크의 두종류가 있다. 이진 탐색 나무와 비슷.

하지만 회전과 분할 필요.

- 흑 : 보통의 링크를 말한다.

- 적 : 3-노드 또는 4-노드에 속하는 노드들을 연결할 때 사용한다.

흑적 나무에서는 어떤 노드의 태그가 적색이면 이 노드의 두 자식 노드의 태그는 모두 흑색입니다.

따라서 뿌리에서 잎까지의 경로상에 2개의 적 링크가 연달아 나타나지 않습니다.

나무의 키의 총 수가 n인 흑적 나무의 가능한 최대 깊이는 O(logn) 이고

흑 또는 적의 색상을 고려하지 않을 때 가장 이상적으로 꽉 채워진 나무의 깊이는 logn g + 1입니다.

이것으로 아무리 잘 만들어져도 뿌리에서 임의의 잎에 이르는 경로에 존재하는 흑 노드의 개수는 logn g+1을 넘을 수 없는 거죠.

-최대 깊이 O(logn)

외부 탐색법

인덱스 순차 접근 - 자료가 미리 정렬된 경우에 인덱스 테이블을 이용하여 검색의 효율을 높이는 검색 방법.

인덱스는 책의 색인과 마찬가지로 특정 키값을 가지는 자료의 위치를 말합니다. 다시 말하면 배열에 정렬되어 있는 자료 중에서 일정

간격으로 떨어져 있는 원소들을 저장한 테이블이라고 할 수 있죠.

이러한 인덱스 된 순차 접근을 사용하기 위해선 주자료 리스트와 인덱스 테이블이 모두 정렬되어 있어야 합니다.

테이블의 크기에 따라 검색의 성능이 달라지고 큰 인덱스 테이블을 사용하면 검색 범위가 작아져 검색의 성능 향상

테이블의 크기가 작으면 그 반대입니다.

배열의 크기를 n, 인덱스 테이블의 크기를 m 라고하면 저장 간격은 n/m 이고 탐색시간은 O(m+n/m)이 됩니다.

B- 나무

바이어와 매크라이트가 1972년에 발표한 논문에서 제안한 방법으로 해싱이 아닌 거의 모든 큰 규모의 파일에서 독점적으로

사용하는 방법입니다. 삽입 삭제 키 범위 탐색을 필요로 하는 프로그램을 위한 표준 파일 로직입니다.

- 모든 리프 노드들을 같은 레벨에 있게 함으로써 항상 높이 균형을 이룸.

- 업데이트와 탐색 연산은 몇 개의 디스크 페이지에만 영향을 미침.

- 나무에 있는 모든 노드가 적어도 어떤 최소비율로 소유하게 되어 공간/탐색/업데이트 연산 시 필요한 디스크 읽기 횟수 줄일수 있음.

- B-나무의 기본적인 연산은 특정 키값의 탐색, 정렬, 삽입, 삭제로 분리할 수 있음.

- 정렬은 나무를 순차적으로 중위 순회를 이용하여 수행.

- 순차 처리는 좋은 성능을 발휘 하지 못함. 특정 키값을 직접 처리할 경우 많이 사용.

- 삽입,삭제 리프노드에서 부터 시작.