B Tree, B+ Tree 그리고 DB Index

- 트리 자료구조의 일종으로 이진트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조

- 이진트리에서 발전되어 모든 리프노드들이 같은 레벨을 가질 수 있도록 자동으로 벨런스를 맞추는 트리

- 이진트리와 달리 하나의 노드에 많은 수의 정보를 가질 수 있고 최대 M개의 자식을 가질 수 있다 하여 M차 B 트리라고도 함

- 데이터베이스와 파이 시스템에서 널리 사용

삽입과정은 다음과 같은 과정이 이루어집니다.

- 삽입 과정에서 노드 분할은 리프노드 검색과 달리 하향식이 아니 상향식으로 이루어집니다.

분할이 일어나지 않는 경우

분할이 일어나는 경우

- B+ 트리는 B 트리를 변형한 알고리즘

- B 트리와 달리 리프 노드에만 데이터를 저장하기 때문에, 모든 노드를 검색하지 않아도 되 효율적으로 검색이 가능

- 내부노드는 오로지 키만 저장

- 리프 노도들은 연결 리스트로 구성되어 있어 순차적인 접근이 용이

B+ Tree 장점

- 범위 검색의 효율성 향상: B+ 트리는 리프 노드에만 데이터를 저장하고 내부 노드는 키만을 저장하므로 범위 검색이 매우 효율적이기 때문에 대용량 데이터 색인에 용이

- B+ 트리는 B 트리와 같이 균형 잡힌 트리이기에, 모든 리프 노드까지 도달하기 위한 경로의 길이가 동일

- 디스크 I/O 감소: 트리는 리프 노드만이 실제 데이터를 가지고 있기 때문에 디스크 I/o를 최소화 할 수 있음

- 순차 엑세스 성능: B+ 트리의 리프 노드는 연결 리스트로 구성되어 있으며, 순차 액세스(Sequential Access)를 지원

B+ Tree 단점

- 단일키 검색시 추가적인 비용: B트리와 달리 B+ 트리에서는 단일 키를 검색할 때에도 리프 노드까지 내려가야 하므로 추가적인 탐색 비용이 발생

- 데이터의 순차적 삽입 및 삭제에 대한 오버헤드: B+ 트리는 삽입이나 삭제 연산이 발생할 때 리프 노드를 조정해야 합니다. 특히 데이터의 순차적인 삽입이나 삭제가 자주 일어나는 경우에는 리프 노드의 재배치나 분ㄴ할 등의 오버헤드가 발생할 수 있습니다.

- 메모리 사용량: B+ 트리는 내부 노드가 자식 노드를 가리키는 포인트를 유지해야하기 때문에 메모리 사용량이 상대적으로 더 많음

B+ 트리 검색과정

- B 트리와 동일

데이터베이스 Index는 데이터의 검색 속도를 향상시키는 자료구조로 B+트리 자료구조를 사용합니다.

SELECT 뿐만아니라 UPDATE, DELETE 등의 자료 색인이 선행되는 연산에서도 더 빠른 속도를 보여줍니다.

인덱스 자료구조의 추가 연산

INSERT: 새로운 데이터에 대한 인덱스를 추가합니다.

DELETE: 삭제하는 데이터의 인덱슬르 사용하지 않는다는 작업을 진행합니다.

UPDATE: 기존의 인덱슬르 상요하지 않음으로 처리하고, 갱신된 데이터에 대해 인덱스를 추가함.

인덱스의 단점

인덱스를 관리하기 위해 DB의 추가 저장 공간이 필요합니다.
인덱스를 관리하기 위해 추가 작업이 필요합니다.
인덱스를 잘못 사용하는 경우 오히려 성능이 저하됩니다.
- INSERT, DELETE, UPDATE가 빈번한 속성 또는 테이블 경우에 인덱스를 사용하게 되면 인덱스의 크기가 커지고 또한 매번 인덱스 자료구조의 B+ 트리 구조가 바뀌기 때문에 오히려 성능이 저하됩니다.
- 또한 DELETE, UPDATE 연산의 경우 기존의 인덱스를 삭제하지 않고, 사요하지 않음 처리를 하기 때문에 해당 연산이 빈번해지면 실제 데이터보다 인덱스가 더 커질 수 있습니다.

인덱스를 사용하면 좋은 경우

- INSERT, UPDATE, DELETE가 자주 발생하지 않는 칼럼

- JOIN, WHERE, ORDER BY에 자주 사용되는 칼럼

창민이 개발일지