B tree 삽입, 삭제 알고리즘과 DB 인덱스

문제상황

DB 칼럼에 시간 칼럼을 넣는것을 잊어서 뒤늦게 createdAt 필드를 추가하고, 기존 필드는 null로 채웠다.

createdAt을 통한 쿼리가 빈번하므로 아래처럼 신규 인덱스를 함께 만들어서 쿼리 효율을 높이기로 했다.

ALTER TABLE mytable
ADD COLUMN createdAt DATE NULL;

CREATE INDEX idx_createdAt ON mytable (createdAt);

근데 B tree와 비슷한 BST 트리를 생각하면, 시간순으로 데이터가 들어오는 경우에는 트리가 점점 한쪽으로 치우치게 되어 O(n)에 가까운 끔찍한 효율성을 가지게되는거 아닌가 하는 생각을 했다.

B tree에서 삽입 삭제는 어떻게 관리되고, 시간 칼럼에 대해 인덱스를 만들때 골고루 들어올 때 보다 불리한 점이 있을지 정리해보았다.

 

B tree와 인덱스

결론부터 말하자면, B tree 데이터구조는 균형잡힌 트리이기 때문에 이러한 상황은 발생하지 않는다.

B-트리는 이진 탐색 트리를 일반화하여 두 개 이상의 자식을 가진 노드를 허용하는 자료구조이다.

페이지 단위로 디스크에서 메모리로 데이터를 불러오는 컴퓨터의 특징을 생각할 때,  BST보다 DB와 파일시스템에서 사용하기 유리한 구조이다.

 

여기에 더해 B 트리에는 지켜야할 규칙들이 있고, 이 규칙을 지키지 못하는 상태가 되면 균형을 맞추기 위한 추가 작업이 수행 된다.

B 트리의 노드가 가질 수 있는 최대 자식수를 M 이라고 할 때, B 트리는 아래 규칙들을 지켜야한다.

1. 각 노드는 최대 M개의 자식을 갖는다.
2. 루트와 리프를 제외한 모든 노드는 최소한 ⌈ m /2⌉개의 자식을 갖는다.
3. 루트 노드는 최소한 두 개의 자식 노드를 갖는다. (리프노드일 때는 제외)
4. 모든 leaf 노드가 같은 높이에 있어야한다.
5. k개의 자식을 갖는 internal 노드에는 k −1개의 키가 있어야한다.

여기에 데이터의 삽입, 삭제를 모두 leaf 노드에서 수행한다는 규칙만 더하면 B 트리의 삽입삭제를 이해할 수 있게된다.

B tree의 삽입 삭제

사실 아래 영상을 보는게 더 빠르게 이해될 수도 있다.

1. [쉬운코드] B tree의 개념과 특징, 데이터 삽입

2. [쉬운코드] B tree 데이터 삭제의 동작방식

 

순차 INSERT 쿼리시 일어나는 일

항상 오른쪽 leaf 노드에서의 삽입이 일어나게되며, leaf 노드가 M개의 키를 갖게되어 노드 분할이 필요한 경우에도 탐색 범위 내의 참조값들을 변경하게된다.

따라서 버퍼풀에 적재된 메모리 캐시를 통해 데이터 삽입을 수행할 확률이 매우 높다.

 

순차 DELETE 쿼리시 일어나는 일

오래된 데이터를 한꺼번에 지울 때, 역시 맨 왼쪽 leaf 노드를 위주로 삭제를 수행하게되며, 부모노드를 통해 다시 balance를 맞추는 경우에도 탐색범위였던 노드를 변경하게된다.

삭제 범위가 한 페이지를 넘어가도, 그 형제노드를 곧 읽을 것을 예측할 수 있으며, 이러한 예측 가능한 페이지 읽기는 버퍼풀 프리패칭 최적화의 수혜까지 받을 수 있다.

 

랜덤 INSERT, DELETE와의 차이

이건 순차 id와 uuid의 장단점을 비교하는 글에서 성능과 확장성에 관련된 내용을 찾아볼 수 있었다.

 

분산환경에서 충돌없는 id생성이 필요한 경우 UUID를 pk로 사용하는 경우가 있다.

이때 uuid로 B-tree를 구성하면 아래와 같은 비효율이 생긴다.

- 물리적 생성 순서와 pk 순서가 일치하지 않는다. 따라서 인덱스 트리에 불필요한 재정렬과 페이지 분할(page splits)을 자주 발생시키게된다.

- 또한 uuid는 128bit로 bigint에 비해 두배나 큰 크기여서 메모리 사용량이 많고, 전체 B-tree 크기를 증가시킨다.

 

재정렬과 페이지 분할 횟수가 증가하는 것은 B 트리의 특성에서 발생하는 단점이므로, 랜덤 insert 및 delete를 수행할 때도 동일하게 적용된다고 볼 수 있다.

 

결론

정리하자면, B-트리는 단순한 이진 탐색 트리와 달리 스스로 균형을 맞추는 자료구조이기 때문에, 시간순으로 createdAt 칼럼에 인덱스를 생성하고 순차적으로 데이터가 들어온다고 해서 한쪽으로 치우친 “O(n) 트리”가 되는 일은 없다.

오히려 순차 입력·삭제의 경우 버퍼풀 캐싱과 프리패칭 최적화까지 더해져 예상 가능한 접근 패턴을 활용할 수 있기 때문에 성능상 유리한 측면이 많다.

 

따라서 시간 기반 쿼리가 잦고, 삭제도 주기적으로 순차적으로 일어난다면 createdAt 인덱스는 성능을 확보하는 좋은 선택이 될 수 있다.

---

참고 자료

- Delete Operation in B-Tree

- UUID vs. Sequential ID as Primary Key