[Backend] DB 인덱스 이해하기

🙋 들어가며

처음 자료구조를 공부할 때 우리는 배열을 가장 먼저 접합니다.

배열에서 데이터가 어디에 있는지 나타낼 때 인덱스라는 용어를 사용하는데,

데이터베이스에서도 이 인덱스라는 용어를 사용합니다.

이번 글을 통해서 인덱스가 무엇이고 어떻게 사용하는지 알아보겠습니다.

---

📚 인덱스란?

저번에 읽었던 책에서 찾고 싶은 내용이 있을 때 어떻게 찾을까요?

맨 앞에 있는 목차혹은 끝에 있는 찾아보기를 참고할 것 같습니다.

그림 1 : 찾아보기

이렇게 빠르게 찾기 위해서 도움을 주는 페이지를 인덱스라고 합니다.

페이지라고 표현한 이유는 DB에서 인덱스는 하나의 자료구조이기 때문입니다.

기본적으로 인덱스는 키를 정렬해서 보관합니다.

🤔 왜 빨라질까?

인덱스를 둔다는 것은 원하는 데이터가 어디에 있는지 마킹해두는 것입니다.

마킹을 기반으로 찾기 때문에 훨씬 빠른 성능을 기대할 수 있습니다.

🙅 인덱스가 필요없는 상황

인덱스가 무조건적으로 좋기만 할까요? 다음 상황들을 고려 해봅시다.

1️⃣ 중복되는 키워드

목차에 “치킨의 역사”, “치킨 만드는 법”, “치킨이란?” 등이 있다고 가정 해봅시다.

여기서 치킨이란 키워드로 찾으려고 하면 어떤 목차를 사용해야 할까요? 모르겠습니다😥

따라서 인덱스는 최대한 중복되지 않는 값을 사용해야 합니다.

2️⃣ 적은 데이터

이번에는 목차가 “치킨이란?” 단 하나만 존재한다고 가정 해봅시다.

이런 경우에서는 목차가 필요할까요? 전혀 필요가 없어 보입니다.

목차를 둔다는 것은 추가적인 페이지가 필요하다는 뜻입니다.

적은 데이터를 가지고 있을 때 인덱스를 두는 것은 의미가 없습니다.

3️⃣ 데이터 추가

책 어딘가에 새로운 내용을 추가해야 한다고 가정 해봅시다.

새로운 내용을 추가하면 기존에 있던 모든 목차를 수정해야 합니다.

다시 말하면 데이터의 수정이 빈번하다면 인덱스를 두는 것은 비효율적입니다.

 

따라서, 인덱스를 적용하기 전에 발생할 수 있는 불필요한 상황을 고려해서 적용시켜야 합니다.

---

🗂️ 인덱스의 종류

우리는 사실 모르는 사이에 인덱스를 잘 사용하고 있었습니다.

어떤 인덱스인지 알아보고 종류를 알아보겠습니다.

🔑 Cluster Index

클러스터링이란, 유사한 것을 묶는 것을 의미합니다.

우리가 잘 사용하고 있는 기본키는 사실 클러스터링 인덱스입니다.

그림 2 : 클러스터 인덱스

기본키의 성질과 클러스터링 인덱스의 특징은 동일합니다. 정리하면 다음과 같습니다.

• 테이블에 하나만 존재한다.
• 키로 정렬되어 있다.
• 그 자체가 데이터이다.

🍂 Non-Cluster Index (Secondary Index)

클러스터링 인덱스를 제외한 나머지 형태를 모두 넌클러스터링 인덱스라고 부릅니다.

그림 3 : 넌클러스터 인덱스

“Non”에서 예상했듯이 클러스터 인덱스와 반대되는 특징을 가집니다. 정리하면 다음과 같습니다.

• 여러 개가 존재할 수 있다.
• 실질적인 데이터는 정렬되어있지 않을 수도 있다.
• 데이터의 주소를 가지고 있다.

🤷‍♂️ 그래서 뭐가 더 좋을까?

사실 어떤 것이 더 좋다고 이야기할 수 없습니다. 상황에 따라 다르기 때문입니다.

이 둘의 장점을 모두 활용하는 방식으로 많이 사용하고 있습니다.

뒤에 나올 B-Tree를 보면서 이야기 해보겠습니다.

---

🏗️ 인덱스의 구조

인덱스를 저장하는 구조는 대표적으로 B-Tree와 Hash-Table이 존재합니다.

그중에서 가장 많이 사용하는 B-Tree에 대해서 알아보겠습니다.

그리고 구조 자체를 이해하기 위해서 페이지라는 개념도 알아보겠습니다.

📄 페이지 (블록)

페이지란, 데이터를 읽고 쓰는 최소 작업 단위입니다. 인덱스라는 자료구조는 페이지의 집합입니다.

페이지의 크기가 어떻게 되는지에 따라서 효율이 결정됩니다.

 

한 인덱스에 10개의 데이터를 저장(페이지의 크기가 10)할 때 조회 시 15개의 데이터를 읽어왔다면

2개의 페이지 즉, 20개의 데이터를 읽어오는 것이기 때문에 페이지의 크기는 성능에 직접적인 영향을 줍니다.

🌲 B-Tree (균형 트리)

인덱스를 저장하는 자료구조입니다. B 때문에 이진트리를 떠올릴 수 있는데 Balanced를 의미합니다.

다음 그림과 같은 구조를 가지고 있는데, 리프 노드에 연결된 값이 실제 데이터의 기본키입니다.

그림 4 : B-Tree

🧩 인덱스 키 추가, 삭제, 수정

B-Tree에서 인덱스 키는 쿼리에 따라서 다르게 데이터베이스에 반영됩니다.

• INSERT :
  • 인덱스를 효율적으로 사용하기 위해서 정렬되어 있어야 합니다.
  • 키를 추가할 때는 적절한 위치를 찾아야 하므로 많은 비용을 소모해서 추가합니다.
• DELETE : 
  • 삭제를 할 때는 간단하게 사용하지 않는다고 마킹을 해둡니다.
  • 단순하게 마킹을 해두면 나중에 처리할 수 있고, 다시 필요하다면 재사용할 수 있습니다.
• UPDATE : 
  • 키가 변경되는 것은 저장된 구조가 변경될 수 있음을 의미합니다.
  • 많은 비용을 요구하므로 이전 키는 삭제(마킹)하고 새롭게 추가합니다.
  • 즉, UPDATE는 INSERT + DELETE로 볼 수 있습니다.

🧐 왜 B-Tree?

왜 B-Tree를 사용할까요? 두 가지 이유가 존재합니다.

1️⃣ 균일성

B-Tree는 균형 트리라서 높은 균일성을 가지고 있습니다.

그림 5 : 균형 트리

균일성의 사전적 정의는 한결 같이 고른 성질을 의미합니다. 즉, 결과가 매번 비슷한 성질입니다.

루트 노드부터 리프 노드까지 거리가 일정한 구조라서 높은 균일성을 가집니다.

인덱스 존재 목적에 가장 부합한 자료구조입니다.

2️⃣ 검색 용이성

Hash-Table는 해시값을 사용합니다.

검색 값이 변경되기 때문에 일부만 검색하거나 범위를 검색할 때는 효율이 떨어집니다.

반면에, B-Tree는 원래 값을 기준으로 검색하기 때문에 DB에 더 적합합니다.

🎄 B+Tree

B-Tree의 문제점을 개선시킨 자료구조입니다.

트리라는 자료구조는 모든 데이터를 확인하기 위해서는 되돌아가야 한다는 문제점이 있습니다.

그림 6 : 트리 구조

위 그림에서 4에서 19를 찾으려면 다음 순서와 같이 돌아가는 것을 확인할 수 있습니다.

이동 순서 : 4 → 10 → 15 → 17 → 19

그렇다면 B+Tree에서는 어떻게 이 문제를 해결하는지 알아보겠습니다.

다음은 B+Tree의 구조입니다.

그림 7 : B+Tree 구조

B-Tree에서 리프 노드끼리 연결시킨 구조가 바로 B+Tree입니다.

이런 구조를 가지기 위해서 한 가지 조건이 추가되었습니다.

바로 중간 노드인 브랜치 노드에는 다음 노드의 위치를 가지도록 했습니다.

 

정리하면, 브랜치 노드에 데이터를 빼고 리프 노드의 데이터를 연결시켜 더 빠른 검색을 제공하는 구조입니다.

---

😎 인덱스 적용하기

인덱스를 적용하는 방법으로 대표적인 두 가지를 소개하겠습니다.

첫 번째는 JPA를 사용하는 방법입니다. 다음과 같이 @Table에 선언 해주면 인덱스를 만들 수 있습니다.

@Table(
  name = "테이블_이름",
  indexes = @Index(name = "인덱스_이름", columnList = "칼럼_이름"))
)

두 번째는 DDL을 작성하는 방법입니다. 사용하는 데이터베이스에 DDL을 다음과 같이 작성 해주면 됩니다.

// MySql 기준
CREATE INDEX 인덱스_이름 ON 테이블_이름 (칼럼1, 칼럼2 ...);

CREATE TABLE 테이블_이름 (
  # 칼럼 ...
  INDEX 인덱스_이름 (칼럼1, 칼럼2 ...)
);

📌 카디널리티(Cardinality)

필요 없는 상황을 고려해서 인덱스를 사용하기로 결정했다면 이제는 카디널리티를 고려해야 합니다.

카디널리티란? 인덱스 키 중에서 고유한(Unique)한 값의 개수를 의미합니다.

예시를 위해서 다음과 같은 테이블을 만들었습니다.

CREATE TABLE person (
  name VARCHAR(30),
  age INT
  INDEX idx_name (name)
);

테이블에 10000건의 데이터가 있다고 가정 해보고 다음 쿼리로 두 가지 상황을 고려 해보겠습니다.

SELECT * FROM person WHERE name = "희조" AND age = 19;

 

Case 1 : 유니크한 값이 10개

한 인덱스당 평균적으로 10000 ➗ 10 = 1000 건의 데이터를 읽어옵니다.

하나를 찾기 위해서 나머지 999건을 의미 없이 읽었습니다.

Case 2 : 유니크한 값이 1000개

이번에는 평균적으로 10000 ➗ 1000 = 10 건의 데이터를 읽어옵니다.

9건만 추가적으로 읽어오면 되므로 이전에 비해서 훨씬 효율적입니다.

이렇게 카디널리티가 높다는 것은 인덱스를 효과적으로 사용하다는 뜻입니다.

---

😋 정리

• 인덱스란 빠르게 찾도록 도와주는 자료구조이다.
• 인덱스는 B-Tree 구조를 가장 많이 사용한다.
• 인덱스를 잘 쓰려면 카디널리티를 고려해야 한다.

---

-Reference : Real-MySQL

 

😋 지극히 개인적인 블로그지만 댓글과 조언은 제 성장에 도움이 됩니다 😋