DB Index 입문
1. Index란?
Index는 DB 분야에 있어서 테이블에 대한 동작의 속도를 높여주는 자료 구조를 일컫는다. Index는 테이블 내 1개의 컬럼, 혹은 여러 개의 컬럼을 이용하여 생성될 수 있다. 고속의 검색 동작뿐만 아니라 레코드 접근과 관련 효율적인 순서 매김 동작에 대한 기초를 제공한다.
DB Index는 흔히 책의 목차에 비유됩니다. 책에 목차가 없다고 가정해봅시다. 독자가 해당 책에서 특정 내용을 찾으려고 한다면 어떤 행동을 취하게 될까요? 책의 첫 페이지부터 시작해서, 원하는 내용이 나올 때까지 모든 페이지를 일일이 찾아 읽을 것입니다. 책의 분량이 적거나 찾고자 하는 내용이 책의 전반부에 위치한다면, 검색에 소요되는 시간이 비교적 짧을 수 있습니다. 그러나 책의 분량이 많거나 찾고자 하는 내용이 책의 후반부에 위치한다면, 검색에 오랜 시간이 걸립니다.
반대로 책에 목차가 존재한다면, 책의 분량이 많더라도 독자는 찾고자 하는 특정 내용이 몇 페이지에 있는지 바로 알 수 있습니다. 이처럼 목차는 검색에 소요되는 시간을 비약적으로 줄여줍니다.
SQL
SELECT * FROM USER WHERE COMPANY_ID = ?DB의 특정 테이블에서 원하는 데이터들을 조회할 때, 조건절에 사용하는 컬럼의 Index가 없다면 어떻게 될까요? 책의 사례와 유사하게, 원하는 데이터의 위치를 특정할 힌트가 없다보니 테이블 전체를 탐색(Full Scan)하게 됩니다. 테이블에 데이터의 양이 많아질수록 검색에 소요되는 시간이 길어집니다.
SQL
CREATE INDEX USER_COMPANY_INDEX ON USER(COMPANY_ID);
#2개 이상의 컬럼을 사용해서 인덱스를 생성할 수도 있다.Index는 데이터의 주소값을 저장하는 별도의 특별한 자료 구조입니다. USER 테이블의 COMPANY_ID 컬럼에 대한 Index가 존재한다면, 예시 쿼리를 수행할 때 테이블 전체를 탐색하지 않고 해당 Index를 바탕으로 원하는 데이터의 위치를 빠르게 검색합니다. Index는 테이블에 있는 하나 이상의 컬럼으로 생성이 가능합니다.
2. 성능 테스트
User.java
//@Table(indexes = {@Index(name = "i_user", columnList = "name")})
@Entity
public class User {
@Id
@GeneratedValue(strategy = GenerationType.IDENTITY)
private Long id;
@Column(unique = true, nullable = false)
private String name;
public User(String name) {
this.name = name;
}
}IndexTest.java
@SpringBootTest(webEnvironment = WebEnvironment.NONE)
class IndexTest {
@Autowired
private UserRepository userRepository;
@Test
void index_test() {
// given
for (int i = 0; i < 1_000_000; i++) {
String randomName = UUID.randomUUID().toString();
User user = new User(randomName);
userRepository.save(user);
}
userRepository.save(new User("tester"));
StopWatch stopWatch = new StopWatch();
// when
stopWatch.start();
userRepository.findByName("tester").get();
stopWatch.stop();
// then
System.out.println(stopWatch.prettyPrint());
}
}- 100만건의 데이터가 존재할 때, 원하는 데이터를 조회하는데 걸리는 시간을 측정하는 테스트 예제입니다.
- 테스트 환경에 따라 검색 성능이 적게는 2배에서 많게는 4배 차이가 났습니다.
- Index 적용 전에는 약 0.22초가 걸립니다.
- Index 적용 이후에는 약 0.12초가 걸립니다.
3. Index 자료 구조
DB Index에 적합한 자료 구조로는 크게 Hash Table, B-Tree, B+Tree 등이 있습니다.
3.1. Hash Table
해시 테이블은 Key-Value로 이루어진 데이터를 저장하는데 특화된 자료 구조입니다. 해시 테이블 기반의 DB Index는 특정 컬럼의 값과 데이터의 위치를 Key-Value로 사용합니다.
해시 테이블은 내부에 버켓이라고 하는 배열이 존재합니다. 해시 함수를 통해 Key를 고유한 해시 값으로 변환시키는데, 이를 버켓 배열의 인덱스로 사용하며 해당 인덱스에 Value를 저장합니다. Key 값으로 Value가 저장되어 있는 위치(주소)를 바로 산출할 수 있기 때문에, 해시 테이 블의 평균적인 시간 복잡도는 O(1)입니다. 하지만 해시 함수를 제대로 정의하지 않으면 해시 함수를 통해 산출한 해시 값이 중복되는 해시 충돌이 발생합니다. 너무 많은 해시 충돌이 발생하면 검색 성능이 하락해 시간 복잡도가 O(N)에 수렴할 수 있습니다.
아울러 Index 자료 구조로 해시 테이블을 사용하는 경우는 매우 제한적입니다. 해시 함수는 Key가 조금이라도 다르면 완전히 다른 해시 값을 생성합니다. 이러한 해시 테이블을 사용하는 Index의 경우 WHERE 조건의 등호(=) 연산에는 효율이 좋지만, 부등호 연산(>, <)은 부적합합니다. 해시 테이블은 내부 데이터들이 정렬되어 있지 않아 탐색이 효율적이지 않습니다.
3.2. B-Tree
B-Tree란 자식 노드가 2개 이상인 트리를 의미합니다. 이진검색 트리처럼 각 Key의 왼쪽 자식은 항상 Key보다 작은 값을, 오른쪽 자식은 큰 값을 가집니다. B-Tree 기반의 DB Index는 특정 컬럼의 값(Key)에 해당하는 노드에 데이터의 위치(Value)를 저장합니다. B-Tree 자료 구조의 상세한 내부 동작 원리는 자료구조 - 그림으로 알아보는 B-Tree을 참조하길 바랍니다.
B-Tree의 Key-Value 값들은 항상 Key를 기준으로 오름차순 정렬입니다. 이로 인해 부등호 연산(>, <)에 대해 해시 테이블보다 효율적인 데이터 탐색이 가능합니다. 또한 B-Tree는 균형 트리(Balanced Tree)로서, 최상위 루트 노드에서 리프 노드까지의 거리가 모두 동일하기 때문에 평균 시간 복잡도는 O(logN)입니다.
그러나 Index가 적용된 테이블에 데이터 갱신(INSERT, UPDATE, DELETE)이 반복되다보면, 트리의 균형이 깨지면서 성능이 악화됩니다.
또한 DB Index 컬럼은 부등호(>, <)를 이용한 순차 검색 연산이 자주 발생합니다. B-Tree가 해시 테이블보다 부등호를 이용한 검색 연산 성능이 좋지만, 순차 검색의 경우 중위 순회를 하기 때문에 효율이 좋지 않습니다. 예시의 경우 7->3->8->1->9->4->10->0->11->5->2->6 순으로 조회하는 등 상당히 많은 노드를 확인해야 합니다.
이러한 연유로 MySQL 엔진인 InnoDB는 B-Tree를 확장 및 개선한 B+Tree를 Index의 자료 구조로 사용합니다.
3.3. B+Tree
B+Tree는 B-Tree를 확장 및 개선한 자료 구조로서, 말단의 리프 노드에만 데이터의 위치(Value)를 관리합니다. 중간 브랜치 노드에 Value가 없어서 B-Tree보다 메모리를 덜 차지하는 만큼, 노드의 메모리에 더 많은 Key를 저장할 수 있습니다. 아울러 하나의 노드에 더 많은 Key를 저장하는 만큼 트리의 높이가 더 낮아집니다.
또한 말단의 리프 노드들끼리는 LinkedList 구조로 서로를 참조하고 있습니다. 따라서 부등호(>, <)를 이용한 순차 검색 연산을 하는 경우, 많은 노드를 방문해야 하는 B-Tree에 비해 B+Tree는 말단 리프 노드 를 저장한 LinkedList를 한 번만 탐색하는 등 속도 이점이 있습니다.
4. 고려 사항
Index를 사용하면 조회 성능이 우수해진다는 것을 알았습니다. 하지만 무턱대고 컬럼에 Index를 적용하는 것은 오히려 성능이 저하되는 역효과가 발생할 수 있습니다.
Index는 항상 최신 상태로 정렬되기 위해, 데이터 갱신(INSERT, UPDATE, DELETE) 작업에 대해 추가적인 연산이 발생합니다.
- INSERT : 새로운 데이터에 대한 인덱스가 추가된다.
- DELETE : 삭제하는 데이터의 인덱스를 제거한다.
- UPDATE : 기존의 인덱스를 제거하고, 갱신된 데이터에 대해 인덱스를 추가한다.
앞서 살펴본 Index 트리 자료 구조는 값이 추가 혹은 삭제될 때마다, 트리 균형을 위해 트리 구조의 재분배 및 합병 등 복잡한 연산이 수반됩니다. 따라서 데이터 갱신보다는 조회에 주로 사용되는 컬럼에 Index를 생성하는 것이 유리합니다.
4.1. Index 대상 컬럼 선정
일반적으로 Cardinality가 높은 컬럼을 우선적으로 인덱싱하는 것이 검색 성능에 유리합니다. Cardinality란 특정 데이터 집합의 유니크(Unique)한 값의 개수를 의미합니다.
- 남-여 등 2가지 값만 존재하는 성별 컬럼은 중복도가 높으며 카디널리티가 낮습니다.
- 개인마다 고유한 값이 존재하는 주민번호 컬럼은 중복도가 낮으며 카디널리티가 높습니다.
Cardinality 높은 컬럼의 경우, Index를 통해 데이터를 더 많이 필터링할 수 있기 때문입니다.