인덱스) B-tree VS B+tree

🌳 Binary Search Tree

Binary Search Tree는 각 노드의 왼쪽 서브트리에는 더 작은 값, 오른쪽 서브트리에는 더 큰 값이 위치하는 이진 트리 구조이다.

Binary Search Tree

이진트리의 확장

이진트리(Binary Tree)는 자식을 최대 2개까지만 가진다. 루트(root) 노드에서 시작하여 왼쪽에는 작은 값, 오른쪽에는 큰 값이 배치된다.

🌳 B-Tree

B-Tree는 널리 쓰이는 인덱스 자료구조 중 하나로, 이진 트리를 확장한 형태이다. 하나의 노드가 가질 수 있는 자식 노드의 수가 2보다 큰 트리 구조이다.

 

단점: 범위 검색(BETWEEN, >=, <=, ORDER BY, LIKE 'abc%') 시 루트에서 여러 번 선형검색을 반복해야 한다.

B-tree

인덱스 중요성

 

---

🌳 B+Tree

B+Tree는 B-Tree의 변형으로 데이터베이스에서 널리 사용되는 자료구조이다.

• B-Tree는 각 노드의 key마다 data를 저장
• B+Tree는 리프 노드에만 data 저장, 비리프 노드는 자식 key값만 저장
• 리프 노드 부모 key는 중복될 수 있음
• 리프 노드는 연결 리스트 구조 → 인접 노드에 바로 접근 가능

B+tree

B+Tree는 B-Tree보다 검색 성능이 개선되어, 특히 범위 검색에서 유용하다. MySQL InnoDB 엔진에서 인덱스를 관리할 때 사용된다.

---

 InnoDB란?

• MySQL의 스토리지 엔진(Storage Engine) 중 하나
• 스토리지 엔진 = MySQL이 데이터를 어떻게 저장하고 관리할지 결정하는 모듈
• MySQL 기본(default) 엔진이 바로 InnoDB

특징: ACID (Atomicity, Consistency, Isolation, Durability) 보장

---

🌳 B+Tree와 InnoDB의 관계

• InnoDB의 인덱스는 B+Tree 구조
• Primary Key 인덱스 = 클러스터드 인덱스 (데이터 자체가 리프 노드에 저장됨)

---

❓ Hash 인덱스는 왜 안 쓰일까?

Hash 인덱스는 = 조건에서는 O(1)로 빠르지만 범위 검색과 정렬을 지원하지 못한다. 따라서 범용적인 SQL DB 인덱스로는 거의 쓰이지 않고, 대신 B+Tree가 표준으로 사용된다.

→ Hash 인덱스는 RDBMS보다는 Redis, DynamoDB 같은 NoSQL에서 많이 활용된다.