snaag commented 6 months ago

Database 의 index

세월이 무심하게도 벌써 3년차 개발자가 되면서 어줍잖게 주워들은 것들이 생겼습니다. 그중에 index 라는 개념이 있습니다. Index 는 말그대로 색인 으로, 빨리 찾는데 도와주는 것으로 알고 있었습니다. 그래서 Index 를 특정 column 에 사용하면, 해당 colum 의 조회 속도가 빨라진다고만 알고 있었습니다.

다만 index 가 어떻게 조회 속도를 빠르게 하는 것이며, 왜 모든 column 에 사용하지 않는 것인지, 단점 은 없는것인지 와 같이 자세히는 모르고있었습니다. 이에 요번에는 index 를 알아보았습니다.

참고자료

DB 흐접에게 넘나 많은 도움을 주신 글들이기에... 맨 위로 올려 짱감사를 표합니당 🙇🏻‍♀️🙇🏻‍♀️

Index 란

인덱스는 결국 지정한 컬럼들을 기준으로 메모리 영역에 일종의 목차를 생성하는 것입니다. - tistory@jojoldu

인덱스는 데이터베이스 테이블에 대한 검색 성능의 속도를 높여주는 자료 구조입니다. 특정 컬럼에 인덱스를 생성하면, 해당 컬럼의 데이터들을 정렬하여 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장됩니다. - tistory@coding-factory

인덱스란 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조이다. - tistory@mangkyu

역시 조회 속도를 높여준다는 내용을 볼 수 있었습니다. 그런데 자료구조 라던가, 메모리 영역에 목차를 생성 한다던가 등 처음 들어보는 내용이 있었습니다.

Index 와 같은 역할을 하는 책 뒤쪽의 색인 에 대해 떠올려보겠습니다. 색인 은 책 뒤편의 Appendix 에 별도의 공간 에서 가나다순 (알파벳순) 으로 찾을 수 있었습니다. 다시 생각해보니, DB 의 인덱스도 다를 것은 없었습니다!

즉 index 를 통해 검색을 빠르게 하려면, 특정 방법으로 정렬이 되어있어야 하고, 이 index 정보가 저장되어있는 별도의 공간이 필요합니다.

Index 는 어떻게 저장되는걸까?

B-Tree

따라서 특정 값보다 크고 작은 부등호 연산에 문제가 없다.

참조 포인터가 적어 방대한 데이터 양에도 빠른 메모리 접근이 가능하다.

데이터 탐색뿐 아니라, 저장, 수정, 삭제에도 항상 O(logN)의 시간 복잡도 를 가진다.

- velog@sem

index 는 B-Tree 자료구조로 저장이 되어있습니다.

index 를 사용하면 조회가 빨라지는 이유

B-Tree 는 조회, 수정, 삭제, 저장 모두 O(logN) 의 시간복잡도를 갖습니다. 따라서 인덱스를 사용하면 빠르게 조회를 할 수 있는 것 입니다. (인덱스를 사용하는 경우) 조회는 인덱스를 통해 PK 를 먼저 찾고, 다음으로 PK 를 통해 레코드를 찾는 순서 로 이루어집니다.

그러나 인덱스를 사용하는 것이 무조건 빠른 조회를 보장하지는 않습니다.

조회 시 1️⃣ PK 를 먼저 찾고, 2️⃣ PK 를 통해 레코드를 찾기 때문에, 인덱스를 사용하는 것이 테이블을 직접 읽는 것 보다 4\~5배 정도 비용이 드는 것 으로 예측된다고 합니다.

그런데 왜 인덱스를 사용하면 빠른걸까요?

(in-memory DB 가 아닌) 데이터베이스는 디스크에 저장을 합니다. 따라서 조회 속도가 많이 느립니다. 데이터가 많아 테이블이 크다면 더 많은 디스크 조회가 있어야 하므로 아주 오래 걸릴 것 입니다.

이 때 PK 를 빠르게 찾아주는 인덱스 를 사용하면, 보다 적은 디스크 조회를 할 수 있습니다. 참고로 oracle 의 경우, 인덱스를 디스크에 저장한다고 합니다.

index 와 카디널리티 (unique)

따라서 인덱스는 디스크 조회 횟수를 줄여, 조회 성능을 높이는 것 입니다. 때문에 인덱스를 사용하였으나 조회할 row 가 많다면, 오히려 index 도 조회하고, 테이블도 많이 조회해야하니 큰 이점이 없습니다. 인덱스를 통해 레코드 1건을 읽는 것이 4\~5배 정도 비싸기 때문에, 읽어야 할 레코드의 건수가 전체 테이블 레코드의 20\~25%를 넘어서면 인덱스를 이용하지 않는 것이 효율적 이라고 합니다.

즉 인덱스도 잘 써야 합니다. 예를들어 성별과 같이 데이터가 크게 식별되지 (unique) 않는 컬럼에 대해 인덱스를 걸어봤자, 데이터가 1/2 로밖에 줄어들지 못합니다. 주민등록번호나 메일주소 등과 같이 식별이 잘 되는 컬럼 에 대해 인덱스를 걸어야 합니다.

이처럼 중복이 낮은 (중복도가 낮은) 것을 카디널리티가 높다 고 합니다. 따라서 인덱스는 카디널리티가 높은 컬럼 을 선택해야 합니다.

따라서 이러한 경우에는 인덱스를 쓰는 것이 좋습니다. 반대의 경우에는 안쓰는 것이 좋겠죠?!

규모가 작지 않은 테이블

INSERT, UPDATE, DELETE가 자주 발생하지 않는 컬럼

JOIN이나 WHERE 또는 ORDER BY에 자주 사용되는 컬럼

데이터의 중복도가 낮은 컬럼

기타 등등

- tistory@mangkyu

DB Engine 과 index

MySQL 의 DB Engine 인 InnoDB 의 B+Tree 구조라고 합니다.

InnoDB에서의 B+Tree는 일반적인 구조보다 더욱 복잡하게 구현이 되었다. InnoDB에서는 같은 레벨의 노드들끼리는 Linked List가 아닌 Double Linked List로 연결되었으며, 자식 노드들은 Single Linked List로 연결되어 있다. - tistory@mangkyu

저는 주로 Oracle 을 사용하기 때문에 Oracle 에 대해서도 찾아봤습니다.

Oracle 은 index 를 DB 에 저장 하지만, 성능을 향상시키기 위해 자주 사용되는 index 는 메모리에 캐시 한다고 합니다. 즉 디스크를 통해 용량과 내구성을, 메모리에 캐싱을 통해 자주 사용되는 index 에 대해 성능을 향상시킬 수 있다고 합니다.

fxzyk commented 6 months ago

서당개도 3년다니면 풍월을 읊는다고.. 주워듣고나서 자세히 알아보는자세 넘나 멋있습니다..! 저와 달리 모범생이시네여 😎

mingnuj commented 6 months ago

전에 단톡에 올라온 그 내용이군여..! 제가 만드는 DB에는 만들지 않은 기능이라 흥미롭게 읽었습니당 나중에 추가될지도... 추가 안했음 좋겠다 ㅎㅎㅎ

dev-writeup-2024 / march

[03-11] Database 의 index #23