프로그래밍공부(Programming Study)/CS-데이터베이스(Database)

DB는 데이터를 어떻게 찾을까? - Full Scan과 B+Tree

Chann._.y 2026. 4. 29.

728x90

데이터베이스 인덱스를 공부하다 보면
가장 먼저 이런 말을 듣는다.

인덱스를 걸면 조회가 빨라진다.

틀린 말은 아니다.
하지만 이 말만 알고 있으면 인덱스를 제대로 이해하기 어렵다.

인덱스는 단순히 "빠르게 해주는 기능"이 아니다.

조금 더 정확히 말하면,

DB가 테이블 전체를 읽지 않기 위해 사용하는 정렬된 자료구조

이다.

이번 글에서는 인덱스를 보기 전에
DB가 데이터를 어떻게 찾는지부터 정리해본다.

1. 인덱스가 없으면 어떻게 찾을까?

예를 들어 이런 테이블이 있다고 하자.

CREATE TABLE users (
    id BIGINT PRIMARY KEY,
    name VARCHAR(50),
    email VARCHAR(100),
    age INT
);

그리고 이런 쿼리를 실행한다.

SELECT *
FROM users
WHERE email = 'chaaany@example.com';

만약 email에 인덱스가 없다면
DB는 어떻게 데이터를 찾을까?

간단하다.

처음부터 끝까지 읽는다.

1번 row 확인
2번 row 확인
3번 row 확인
...
마지막 row 확인

이걸 Full Table Scan이라고 한다.

Full Table Scan은 테이블 전체를 읽으면서 조건에 맞는 row를 찾는 방식이다.

데이터가 100건이면 괜찮다.
1,000건도 괜찮을 수 있다.

하지만 1,000만 건이면 이야기가 달라진다.

email 하나 찾자고
1,000만 row를 전부 확인해야 할 수도 있다.

문제는 여기서 시작된다.

2. Full Scan이 느린 이유

Full Scan이 느린 이유는 단순하다.

너무 많이 읽기 때문이다.

DB 성능에서 중요한 비용 중 하나는 I/O다.

I/O는 데이터를 읽고 쓰는 작업을 말한다.
DB 입장에서는 디스크나 메모리에서 필요한 데이터를 가져오는 일이다.

조건에 맞는 row가 1개뿐이어도
인덱스가 없다면 DB는 그 1개를 찾기 위해 많은 row를 확인해야 한다.

원하는 데이터: 1건
읽어야 하는 데이터: 전체 테이블

이 구조가 비효율적이다.

그래서 DB는 이런 생각을 한다.

매번 전체를 읽지 말고, 미리 찾기 좋은 구조를 만들어두자.

그 구조가 바로 인덱스다.

3. 인덱스는 무엇인가?

인덱스는 책의 색인과 비슷하다.

책 뒤쪽에 이런 색인이 있다고 해보자.

B+Tree .......... 32p
Index ........... 45p
Transaction ..... 80p

우리는 특정 단어를 찾기 위해 책 전체를 처음부터 읽지 않는다.
색인을 보고 바로 해당 페이지로 이동한다.

DB 인덱스도 비슷하다.

email 값                    row 위치
--------------------------------------
a@example.com               row_id=10
b@example.com               row_id=25
chaaany@example.com         row_id=31
d@example.com               row_id=7

즉, 특정 컬럼 값을 기준으로
어디에 row가 있는지 빠르게 찾을 수 있도록 만든 구조다.

여기서 중요한 점은 이것이다.

인덱스는 원본 데이터 자체가 아니라, 원본 데이터를 찾기 위한 별도 구조다.

4. 그런데 왜 B+Tree를 쓸까?

인덱스를 그냥 배열로 만들 수도 있을 것 같다.

[a@example.com, b@example.com, c@example.com, ...]

정렬된 배열이면 이진 탐색을 할 수 있다.

하지만 DB는 단순 배열만으로는 부족하다.

DB 데이터는 계속 변한다.

INSERT
UPDATE
DELETE

데이터가 계속 들어오고, 바뀌고, 삭제된다.

정렬된 배열은 중간 삽입과 삭제에 약하다.
중간에 값을 하나 넣으려면 뒤쪽 데이터를 많이 밀어야 한다.

그래서 DB는 보통 B-Tree 또는 B+Tree 계열 자료구조를 사용한다.

5. B-Tree와 B+Tree

B-Tree와 B+Tree는 모두 트리 구조다.

트리 구조는 위에서 아래로 내려가며 데이터를 찾는 구조다.

가장 위에는 Root가 있고,
중간에는 Branch가 있고,
가장 아래에는 Leaf가 있다.

Root
  └── Branch
        └── Leaf

DB 인덱스에서는 특히 B+Tree가 자주 등장한다.

B+Tree의 큰 특징은 다음과 같다.

1. 실제 데이터 위치는 주로 Leaf Node에 모여 있다.
2. Leaf Node들이 서로 연결되어 있다.
3. 그래서 범위 검색에 유리하다.

그림으로 보면 이런 느낌이다.

                 [Root]
              email < m
              /       \
             /         \
      [Branch]         [Branch]
     a~l 범위          m~z 범위
       /  \              /  \
   [Leaf][Leaf]      [Leaf][Leaf]

각 역할은 다음과 같다.

Root Node   : 탐색이 시작되는 지점
Branch Node : 어느 범위로 내려갈지 결정하는 중간 지점
Leaf Node   : 실제 인덱스 값과 row 위치가 있는 지점

DB는 원하는 값을 찾기 위해
Root부터 시작해서 Leaf까지 내려간다.

6. 실제 검색 흐름

예를 들어 email = 'chaaany@example.com'을 찾는다고 하자.

DB는 대략 이렇게 움직인다.

1. Root Node를 읽는다.
2. chaaany@example.com이 어느 범위인지 판단한다.
3. 해당 Branch Node로 내려간다.
4. 다시 범위를 판단한다.
5. Leaf Node에 도착한다.
6. Leaf Node에서 email 값을 찾는다.
7. 연결된 row 위치로 실제 데이터를 읽는다.

코드로 표현하면 이런 느낌이다.

def find_by_index(root, target_email):
    page = root

    while not page.is_leaf:
        page = page.find_child(target_email)

    entry = page.find_entry(target_email)

    if entry is None:
        return None

    return read_table_row(entry.row_id)

핵심은 이것이다.

테이블 전체를 읽지 않는다.
정렬된 트리 구조를 따라 필요한 위치로 이동한다.

7. 왜 빠른가?

B+Tree는 한 노드에 여러 key를 담는다.

그래서 데이터가 많아져도
트리의 높이가 생각보다 크게 증가하지 않는다.

예를 들어 1,000만 건의 데이터가 있어도
Root -> Branch -> Leaf 정도의 몇 번 접근으로 원하는 위치에 도달할 수 있다.

Full Table Scan
- 최대 1,000만 row 확인

Index Scan
- Root 읽기
- Branch 읽기
- Leaf 읽기
- 실제 row 읽기

차이가 크다.

인덱스가 빠른 이유는
마법 같은 최적화가 있어서가 아니다.

읽어야 하는 데이터의 양을 줄이기 때문이다.

8. 범위 검색에도 유리하다

B+Tree는 등호 검색뿐 아니라 범위 검색에도 강하다.

예를 들어 이런 쿼리가 있다.

SELECT *
FROM users
WHERE age BETWEEN 20 AND 29;

age에 인덱스가 있다면
DB는 먼저 age = 20 근처의 Leaf Node를 찾는다.

그 다음부터는 Leaf Node를 순서대로 읽는다.

[18, 19] -> [20, 21, 22] -> [23, 24, 25] -> [26, 27, 28, 29] -> [30, 31]

B+Tree의 Leaf Node들은 보통 서로 연결되어 있다.

그래서 시작 지점만 찾으면
그 다음은 순차적으로 읽을 수 있다.

이게 범위 검색에서 B+Tree가 강한 이유다.

9. 그림으로 다시 정리

인덱스가 없을 때:

users table

[row1] -> [row2] -> [row3] -> [row4] -> ... -> [rowN]
  확인     확인     확인     확인              확인

인덱스가 있을 때:

idx_users_email

        [Root]
          |
      [Branch]
          |
       [Leaf]
          |
       row_id=31
          |
     users table row

차이는 명확하다.

Full Scan  : 전체를 훑는다.
Index Scan : 찾기 좋은 구조를 따라간다.

10. 핵심 요약

인덱스를 이해하기 전에
먼저 Full Scan과 B+Tree를 이해해야 한다.

정리하면 다음과 같다.

1. 인덱스가 없으면 DB는 테이블 전체를 읽을 수 있다.
2. 이것을 Full Table Scan이라고 한다.
3. Full Scan은 데이터가 많아질수록 느려진다.
4. 인덱스는 특정 컬럼 기준으로 정렬된 검색용 자료구조다.
5. DB 인덱스는 보통 B+Tree 계열 구조를 사용한다.
6. B+Tree는 Root -> Branch -> Leaf 순서로 탐색한다.
7. 인덱스가 빠른 이유는 덜 읽기 때문이다.

한 줄로 정리하면 이렇다.

인덱스는 DB가 전체를 보지 않고, 필요한 위치로 바로 가기 위해 만든 길이다.

다음 글에서는
이 B+Tree 구조를 바탕으로 단일 인덱스가 어떻게 동작하는지 정리해본다.