어..................
면접에서 인덱스에 관련한 질문을 제대로 답을 못해서
제가 너무 CS지식이 부족하다고 느껴서 면접에서 질문했던 것들을 공부하기 위해 이 글을 쓰게 되었습니다.

Index란?

Index란 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조이다. 저희가 특정 데이터에 대해 검색을 한다고 하면 모든 데이터들을 확인을 해야겠죠?
하지만 Index가 있다면 책의 페이지를 보듯이 빠르게 찾을 수 있습니다. (진짜 책 목차랑 완전 똑같다고 보시면 될 것 같습니다.)

Index를 사용하지 않은 데이터를 검색하게 된다면 전체를 탐색하는 Full Scan을 수행해야 합니다. 당연히 모든 데이터를 확인해야 하기 때문에 처리 속도가 떨어집니다.

Index 장/단점

장점

• 데이터들이 정렬되어 있습니다.
• 이미 정렬되어있다는 특성 떄문에 WHERE, ORDER BY, MIN, MAX 의 효율성이 높아집니다.
• 테이블을 조회하는 속도와 그에 따른 성능을 향상시킬 수 있습니다.
• 전반적인 시스템의 부하를 줄일 수 있습니다.

단점

• Index를 관리하기 위해 DB의 약 10%에 해당하는 저장공간이 필요합니다.
• Index를 관리하기 위해 Index 관리 작업이 필요합니다.
• Index를 잘못 사용할 경우 오히려 성능이 저하되는 역효과가 발생할 수 있습니다.
• Index는 테이블의 전체 데이터 중에서 10~15% 이하의 데이터를 처리하는 경우에만 효율적이고 그 이상의 데이터를 처리할 땐 Index를 사용하지 않는 것이 더 낫습니다.

Index 관리

DBMS는 Index를 항상 최신으로 정렬 상태로 유지해야 원하는 값을 빠르게 탐색할 수 있습니다. 그렇기 때문에 Index가 적용된 데이터에 INSERT, UPDATE, DELETE가 수행된다면 각각 다음과 같은 Index 처리과정을 추가적으로 해주어야 합니다.

• INSERT: 새로운 데이터에 대한 Index를 추가함
• DELETE: 삭제하는 데이터의 Index를 사용하지 않는다는 작업을 진행함
• UPDATE: 기존의 데이터에 해당하는 Index를 사용하지 않게 처리하고, 갱신된 데이터에 대해 Index를 추가함

주의사항

UPDATE, DELETE는 Index를 없애는게 아닌 사용하지 않게 처리를 하기 때문에 UPDATE, DELETE가 빈번히 발생을 한다면 데이터는 5000개가 있다고 해도 Index의 크기는 10만개가 될수도 있습니다.
(극단적인 예시)

어디에 Index를 적용하면 좋을까?

• 어느정도의 규모가 있는 테이블
• INSERT, UPDATE, DELETE가 자주 발생하지 않는 테이블 == SELECT가 자주 발생하는 테이블
• JOIN이나 WHERE 또는 ORDER BY에 자주 사용되는 테이블
• 데이터의 중복도가 낮은 테이블

Index 구조

Index는 다양한 자료구조들로 구현을 할 수있는데 여기서는 가장 대표적인 B+Tree 와 Hash 테이블을 알아보도록 하겠습니다.

B+Tree

B+Tree는 DB의 Index를 위해 자식 노드가 2개 이상인 B-Tree를 개선시킨 자료구조입니다.
구조는 위와 같이 Root, Branch, Leaf Node로 구성되며 계층적 구조를 갖고 있습니다.
B+Tree는 모든 노드에 데이터를 저장했던 B-Tree와 다르게 밑에와 같은 특성을 가지고 있습니다.

• Leaf Node만 Index와 함께 데이터를 가지고 있고, 나머지 노드인 Index Node들은 데이터를 위한 Index만을 갖는다.

• Leaf Node들은 LinkedList로 연결되어 있다.

• 데이터 노드 크기는 Index Node의 크기와 같지 않아도 된다.

• Leaf Node를 제외하고 데이터를 가지지 않기 때문에 메모리 공간의 확보로 더 많은 key들을 가질수 수 있습니다. 따라서 노드당 많은 key를 보유할 수 있기 때문에 트리의 높이는 낮아지게 됩니다.

• Full Scan 시, B+tree는 Leaf Node에 데이터가 모두 있기 때문에 한 번의 선형탐색만 하면 되기 때문에 B-tree에 비해 빠릅니다. (B-tree는 모든 노드 확인해야함.)

Hash 테이블

Hash 테이블은 Key, Value로 데이터를 저장하는 자료구조 중 하나로 빠른 데이터 검색이 가능합니다.
Hash 테이블 기반의 DB Index는 (데이터, 데이터의 위치) -> (Key, Value)로 사용하여 컬럼의 값으로 생성된 Hash를 통해 Index를 구현합니다. Hash 테이블의 시간복잡도는 O(1)로 매우 빠른 검색을 지원합니다.

하지만 DB Index에서 Hash 테이블이 사용되는 경우는 제한적입니다. 이유는 Hash가 등호(=) 연산에만 특화되어 있고 부등호 연산(>, <)에 적합하지 않기 때문입니다. 부등호 연산(>, <)이 자주 사용되는 데이터베이스 검색에서는 Hash 테이블이 적합하지 않습니다.

Ascending index vs Descending index

• Ascending index : 작은 값의 인덱스 키가 B-Tree의 왼쪽으로 정렬된 Index
• Descending index : 큰 값의 인덱스 키가 B-Tree의 왼쪽으로 정렬된 Index

또 Scan 방식에 대해서 이해를 하고 넘어갈 필요가 있습니다.

• Forward Index Scan (Forward scan) : Index Key의 크고 작음에 관계없이 Index Leaf Node의 왼쪽 페이지부터 오른쪽으로 스캔 (왼쪽 -> 오른쪽)
• Backward Index Scan (Backward scan) : Index Key의 크고 작음에 관계없이 Index Leaf Node의 오른쪽 페이지부터 왼쪽으로 스캔 ( 오른쪽 -> 왼쪽)

Scan에 따른 성능적 차이

Ascending index로 설정된 테이블이 존재하고 저희는 모든 데이터를 얻는 것이 필요하다고 가정합니다.
풀스캔을 하는 쿼리를 날리는 경우는 2가지 입니다.
ORDER BY index_column ASC, ORDER BY index_column DESC
각각 Forward Scan, Backward Scan에 해당합니다.
카카오 자료 결과에 따르면 1천2백여만건을 스캔한 결과가 각각 4.15, 5.35초로 약 1.2초 차이가 난다고 합니다. (InnoDB 기준)

InnoDB 스토리지 엔진에서는 페이지 잠금 과정에서 데드락을 방지하기 위해서 B-Tree의 왼쪽에서 오른쪽 순서(Forward)로만 잠금을 획득하도록 하고 있다. 그래서 Forward index scan에서는 다음 페이지 잠금 획득이 매우 간단하지만, Backward index scan에서 이전 페이지 잠금을 획득하는 과정은 상당히 복잡한 과정을 거치게 된다.
이런 차이로 인서 많은 페이지를 스캔해야 하는 Index scan에서는 잠금 획득으로 인한 쿼리 처리 지연이 발생하게 된다. (feat. Kakao Tech)

카카오가 말한 Scan에 따른 성능적 차이는 Backward Index Scan 방식이 Forward Index Scan 방식보다 느리다고 합니다.

참고한 Kakao Tech Link

어떤 방식을 사용해야 하나

일반적으로 Index를 ORDER BY ... DESC하는 쿼리가 드물게 실행되는 경우라면, Descending index를 굳이 선택할 필요는 없어 보입니다.

게시물 테이블 같은 경우는 최신순으로 불러오는 성격이기 때문에 이와 같은 테이블은 Descending index 사용하는 것이 적합해 보입니다.

즉 테이블 성격을 고려하여 정렬방식에 따른 얼마나 많은 데이터가 발생하냐에 따라서 Index 방식을 설정하면 될 것 같습니다.

느낀 점

Index가 조회떄문에 사용한다는 것은 알고있었는데
어떠한 특징때문에 조회에 유리하다! 라는점은 이번에 배우게되네요
(사실 해당 내용을 학교 수업과정에서 배우긴했는데.... 까먹어서.. 다시 공부하였네요 ㅠㅠㅠ)

이번에 면접에서 물어본 오름차순, 내림차순 Index에 관해 언제 사용하냐고 질문을 받아 답변을 못했었는데요.
답변을 못했던 것 때문에 기회삼아 공부해 보았습니다.
공부를 하면서 되게 Index 방식들마다 왜 선택해야 하는지에 대해 알게되어서 나중에 테이블 설계 할때 이러한 점을 고려해서 생성을 할 것 같네요.
매우 좋은 공부 경험이었습니다.