B-Tree 구조와 키 변경

MySQL 문서에서는 보통 B-Tree라 부르지만, InnoDB 인덱스의 모양은 B+Tree에 가깝다. B+Tree는 실제 데이터가 트리 맨 아래 단계인 리프 노드(leaf node)에만 있고, 리프끼리 서로 연결된 B-Tree 변형이다. 이 구조 하나로 같은 값 찾기(동등 조회), 범위 조회, 정렬된 순서로 읽기를 모두 처리한다.

구조: 정렬된 페이지들의 트리

다이어그램 로딩…

• 루트·브랜치(내부 노드): 루트(root)는 트리 맨 위 노드, 브랜치(branch)는 루트와 리프 사이의 중간 노드다. 둘 다 실제 데이터 없이 키 범위와 자식 위치만 들고, 찾는 키가 어느 자식 쪽에 있는지 표지판처럼 안내한다.
• 리프: 정렬된 키를 들고 있다. 행 데이터를 PK(Primary Key, 기본 키) 순서로 저장한 클러스터링 인덱스(clustered index)의 리프에는 행 전체가, PK가 아닌 칼럼으로 만든 세컨더리 인덱스(secondary index)의 리프에는 행을 찾아갈 PK 값(클러스터링 키)이 들어 있다. 리프는 이웃 리프와 양방향 링크드 리스트(doubly linked list)로 연결된다. 그래서 범위 스캔은 트리를 다시 타지 않고 옆 리프로 넘어가며 읽고, 같은 연결을 거꾸로 따라가면 역순 스캔이 된다.
• 균형 유지: 모든 리프의 깊이가 같아서 어떤 키를 찾든 거치는 단계 수가 같고, 그래서 탐색 비용이 일정하다. 수천만 건도 보통 3~4단계면 닿는다.

InnoDB에서 트리의 노드 하나는 페이지(page) 하나이고, 페이지 크기는 기본 16KB다. 한 페이지에 키가 수백 개 들어가므로 노드 하나가 가리키는 자식 수, 즉 팬아웃(fan-out)이 크다. 팬아웃이 크면 한 단계 내려갈 때마다 후보가 크게 줄어 트리가 낮아지고, 낮은 트리는 적은 페이지만 읽고도 원하는 키에 닿는다. B-Tree 탐색이 빠른 이유는 이렇게 트리가 낮기 때문이다.

키 추가와 삭제: 분할과 병합

• 삽입: 키 순서에 맞는 리프 페이지를 찾아 넣는다. 페이지가 가득 차 있으면 페이지 분할(page split)이 일어난다. 페이지의 절반을 새 페이지로 옮기고, 새 페이지를 가리키는 키를 부모 노드에 올리는 작업이다. 부모도 가득 차 있으면 부모가 다시 분할되고, 이렇게 분할이 루트까지 번지면 트리 깊이가 1 늘어난다.
• 삭제: 키를 지워도 페이지를 바로 없애지 않고 빈 공간으로 남겨 둔다. 빈 공간은 나중에 들어오는 키가 재사용하고, 비는 정도가 심하면 이웃 페이지와 합치는 병합(merge)이 일어난다.
• UPDATE: 인덱스 키 칼럼 값이 바뀌면 정렬 위치가 달라지므로, 기존 인덱스 항목(entry)을 지우고 새 항목을 삽입하는 것과 같다. 이와 별개로, 값이 무작위인 랜덤 UUID(Universally Unique Identifier, 범용 고유 식별자)를 PK로 쓰면 새 행도 리프 끝이 아니라 중간 곳곳에 흩어져 들어간다. 그래서 페이지 분할이 잦아지고 캐시 미스(cache miss)도 늘 수 있다.

분할과 병합은 페이지에 잠금을 걸고 디스크 I/O(Input/Output, 입출력)를 일으킨다. AUTO_INCREMENT처럼 자동으로 커지는 순차 키는 새 키가 늘 맨 끝 리프에 붙으므로 분할이 적어 B-Tree에 친화적이다. 반면 랜덤 키는 여기저기 끼어들며 분할을 부르므로 비친화적이다. PK를 순차 키로 할지 랜덤 키로 할지에 대한 설계 논쟁도 이 차이에서 나온다.

면접 포인트

• "B-Tree가 해시보다 좋은 점?" → 범위·정렬·LIKE 접두어 검색(LIKE 'abc%'). 해시 인덱스(hash index)는 키를 해시값으로 바꿔 한 번에 찾는 구조라 동등 조회 전용.
• "UUID PK가 왜 문제인가요?" → 리프 중간 삽입 → 잦은 분할 → 단편화(fragmentation)·캐시 미스. 순차 키와 대비.
• "리프가 링크드 리스트인 이유?" → 범위 스캔을 트리 재탐색 없이 옆으로 이동하며 처리.