CS

S)DB_07_B tree, B+tree

99duuk 2024. 3. 30. 15:41

Binary tree

각 노드가 최대 두 개의 자식을 가질 수 있는 트리 구조다.

 

평균적인 시간 복잡도로 O(logN)을 갖지만

한쪽 방향으로만 노드들이 쏠려 균형이 맞지 않은 경우 최악의 시간복잡도로 O(N)을 갖게 된다. 

 

노드 하나의 자식 노드로 최대 두 개의 노드만 가질 수 있으므로

데이터가 증가할 수록 깊이가 커지는 속도가 빠르다.

 


 

 

B tree & B+tree

데이터를 효율적으로 저장하고 탐색하기 위한 트리 기반의 자료구조

Balanced, 트리의 노드가 한쪽으로만 쏠리지 않도록

노드 삽입  삭제 시 특정 규칙에 맞게 재정렬해 전체적으로 균형을 유지한다.

 

 삽입 과정 : 

빈 트리에 데이터 삽입할 때는 새로운 노드 생성하고,

가득 찬 노드 경우 분할 통해 새로운 노드 생성한다.

 

 삭제 과정 : 

삭제할 key가 리프 노드에 있는 경우 해당 노드에서 삭제를 진행하며,

리프 노드가 아닌 경우에 key를 찾아 해당 리프 노드로 이동해 삭제한다. 

 

 

 

ex)

- B트리는 도서관 책장의 책처럼 정렬되어 있어 빠르게 원하는 책을 찾을 수 있다.

하지만 그 정해진 책장의 위치를 찾는데 시간이 걸린다.  

 

- 만면 B+트리는 도서 목록이 있는 색인처럼 동작한다.

책장 전체를 통째로 훑을 번거로움 없이 책의 위치를 빠르게 찾을 수 있다. 

 


 

B tree는 

- 데이터가 정렬된 상태로 유지되어 있는 트리 구조이다. 

          => 항상 정렬된 상태로 특정 값보다 크고 작은 부등호 연산에 문제가 없다.

- 각 노드가 여러 개의 키와 해당 키에 대한 자식 포인터 가지는 트리이다.

- 자식 노드 여러 개 존재 가능하다.

          => 균일성, 어떤 값에 대해서라도 같은 시간에 결과를 얻을 수 있다.

- 모든 리프 노드가 동일한 레벨에 있어야 한다.

          => 균형 트리 (성능이 안정화 되어 있다. 모든 리프 노드까지 거리 일정해 검색 시간 일정하게 유지된다.)

- 각 노드는 일정한 차수 가지고 있어야 한다. 

- 모든 노드를 방문해야 검색, 삽입, 삭제 할 수 있다.

 

용도

□ 범용 데이터베이스 인덱스

: 데이터베이스에서 인덱싱에 널리 사용된다.

범용적이고 여러 유형의 쿼리와 작업에 대해 균일한 성능을 제공하기 때문 

 

 파일 시스템 

: 파일 시스템에서 디렉터리 구조 유지하고 파일을 관리하는데 사용된다. 

이를 통해 파일 시스템이 크기가 큰 디렉터리를 효율적으로 관리할 수 있다.

 

외부 메모리 데이터 구조 

: 대용량 데이터베이스나 파일 처리하는데 적합하다.

외부 메모리에서도 효율적으로 동작하므로 디스크 기반의 데이터 구조로 사용된다. 

 

 

 

 

어떤 한 데이터 검색에서 B-tree는 빠를 수 있다. 

하지만! 모든 데이터를 순회하기 위해서는 리프 노드까지 갔다가 다시 부모 노드로 BackTracking하여

트리의 모든 노드를 방문해야 하므로 비효율적이다. 

이러한 단점을 보완한 것이 !!! B+tree이다.

 

 

B+tree는 

 

- B tree의 확장 형태, 데이터 항목은 리프 노드에만 저장된다. 

          => 중간 노드들은 자식 노드로 향하는 포인터만 갖는다. 

          => 저장 공간 절약해 더 많은 포인터 저장할 수 있다. 

          → 한 노드가 가질 수 있는 자식 노드의 최대 개수 늘릴 수 있어, 트리의 depth를 낮출 수 있다.

- 내부 노드(나머지 노드)는 데이터를 위한 키만저장하고 실제 데이터는 리프 노드에서만 찾을 수 있다.

          => 메모리의 효율적 사용, 리프 노드 제외하고 데이터 담지 않아 메모리 확보 더 할 수 있고, 더 많은 key를 수용할 수 있다.

          => 하나의 노드에 더 많은 Key를 담을 수 있기 때문에 트리 높이가 낮아진다 (=cashe hit rate 높아짐)

          => 노드들이 갖는 key는 중복될 수 있다.

- 모든 리프 노드는 Linked List로 연결 되어 있다. 

          => 풀 스캔이나 범위 검색 시 빠른 성능 보장한다.  

- 풀 스캔 시, B+tree는 리프노드에 데이터가 모두 있기 때문에 한 번의 선형 탐색만 하면 된다. 

          => Linked List로 연결된 리프 노드에 대해서만 읽기 진행하면 된다. -> B tree에 비해 빠르다. 

- 범위 검색에효율적이며, 범위 검색이 일반적인 OLTP(온라인 트랜잭션 처리) 작업에서 많이 사용된다. 

 

 

- 실제 데이터에 접근하기 위해서는 무조건 트리 맨 아래에 있는 리프 노드까지 접근해야 한다. 

        => 추가 접근 시간 소요, 추가 저장 공간이 필요, 순차 접근에 제약, 자주 사용되지 않는 데이터 대한 비용 발생

더보기

- 추가 접근 시간 소요

  : 트리의 깊이 따라 리프 노드까지 경로 길어질 수 있다. 특히 디스크 기반의 파일 시스템에서는 디스크 I/O 작업이 많아질 수 있다.

 

- 추가 저장 공간이 필요

  : 데이터가 리프 노드에만 저장되므로 추가적인 저장 공간이 필요하다. 데이터베이스나 파일 시스템에서 효율적 공간 관리 어렵게 할 수도 있다. 

 

- 순차 접근에 제약

  :  범위 쿼리나 순차 접근에 적합하지만, 특정 위치의 데이터에 접근하는 데 있어서는 추가적인 탐색 과정이 필요하다. 순차 접근이 아닌 경우에는 약간의 오버헤드가 발생할 수 있다. 

 

- 자주 사용되지 않는 데이터 대한 비용 발생

  : 모든 데이터가 리프 노드에 저장되기 때문에 자주 사용되지 않는 데이터도 메모리나 디스크 공간을 차지하게 된다. 저장 공간의 낭비가 발생한다.

 

 

[cashe hit rate]

더보기

캐시에서 요청된 데이터 찾을 수 있는 비율, 높을 수록 캐시의 성능이 좋음을 나타냄

 

 

 데이터베이스 인덱스의 범위 쿼리

: 범위 쿼리를 처리하는 데 특히 유용하다.

데이터베이스 쿼리는 B+tree의 특성을 최대한 활용해서 효율적으로 처리된다. 

 

정렬된 시퀀스의 관리

: 데이터베이스의 클러스터링 인덱스 또는 정렬된 파일에서 자주 사용된다.

 

 외부 정렬

: 외부 정렬 알고리즘에서 사용되는 주요 데이터 구조중 하나이다. 

대용량의 정렬된 데이터를 디스크에 저장하고 효율적으로 정렬하는 데 이용된다. 

 

 


  B-tree B+tree
데이터 저장 ALL 노드에 저장 ONLY 리프 노드 저장
key 중복 중복 X 중복 존재 가능
Full Scan ALL 노드 순회하며 탐색 linked list 통해 리프 노드만 선형 탐색
key 통한 탐색 리프 노드까지 가지 않아도 되는 경우 있음 무조건 리프 노드까지 가야 함
높이  비교적 높음 비교적 낮음 

 

 

 

 

 

Q> 데이터 검색을 할 때, index를 B+tree로 구현하는 이유는? (hash table의 시간복잡도가 O(1), b+tree가 O(log n)으로 더 빠른데?)

A> 해시 테이블은 등호 연산에 특화되어 있어서 단일 값에 대한 조회가 빠르지만, 범위 쿼리나 부등호 연산 같은 경우에는 효율적이지 않다. 

그에 반해 트리는 데이터를 정렬하여 저장하기 때문에 범위 쿼리나 부등호 연산에 효과적이다. 

또한 데이터를 메모리 내에서 순차적으로 접근할 수 있도록 구조화되어 있어서 캐시 효율성이 높다. 

 

 

더보기

범위 쿼리 : 

특정 범위 내에 있는 데이터를 검색하는 작업

이러한 작업은 B+트리와 같은 효율적 자료구조에서 잘 처리된다. 

B+트리는 리프 노드에 연결된 Linked List를 통해 범위 쿼리를 빠르게 처리할 수 있다. 

 

 

해시 테이블 : 키 & 주소 

 

 

 

 

 

 

'CS' 카테고리의 다른 글

S)DB_08_JOIN  (0) 2024.04.02
S)DB_08_DBCP  (0) 2024.04.02
S)DB_07_인덱스  (1) 2024.03.30
S)DB_06_트리거  (1) 2024.03.27
S)DB_06_저장 프로시저  (1) 2024.03.27