DB에서 인덱스를 잘 사용하면 어떤 장점이 있을까요?

2-1. 인덱스(Index)란?

• 데이터베이스의 테이블에 대한 검색 속도를 향상시켜주는 자료구조이다.
• 테이블의 특정 컬럼(Column)에 인덱스를 생성하면, 해당 컬럼의 데이터를 정렬한 후 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장된다. 컬럼의 값과 물리적 주소를 (key, value)의 한 쌍으로 저장한다. 해당 키에 대하 물리적주소가 가리키는 원본테이블의 행을 가져온다.

  인덱스는 특정 컬럼을 복사하여 정렬한 컬럼의 복사본이다.

인덱스는 책에서의 목차 혹은 색인이라고 생각하면 된다. 책에서 원하는 내용을 찾을 때 목차나 색인을 이용하면 훨씬 빠르게 찾을 수 있는데

이때 ,
책의 내용 = 데이터
책의 목차 = 인덱스
책의 페이지 번호 = 물리적주소

라고 생각 할 수 있다.

원하는 내용(데이터)을 찾기 위해 목차(인덱스)에 보고 해당 목차에 대한 페이지 번호(물리적주소)를 보고 데이터를 찾을 수 있다.

2-2. 인덱스의 자료 구조

2-2-1. 해시 테이블

1. 해시 테이블(Hash Table)

해시 테이블은 key와 value를 한 쌍으로 데이터를 저장하는 자료구조이다. (key, value)로 쌍을 표현하며, key값을 이용해 대응되는 value값을 구하는 방식이다. 해시 충돌이라는 변수가 존재하지만 평균적으로 O(1)의 매우 빠른 시간만에 원하는 데이터를 탐색할 수 있는 구조이다.
해시 테이블을 이용한다면 인덱스는 (key, value) = (컬럼의 값, 데이터의 위치)로 구현하는데, 해시 테이블은 실제로 인덱스에서 잘 사용되지 않는다.

그 이유는, 해시 테이블은 등호(=) 연산에 최적화되어있기 때문이다. 데이터베이스에선 부등호(<, >) 연산이 자주 사용되는데, 해시 테이블 내의 데이터들은 정렬되어 있지 않으므로 특정 기준보다 크거나 작은 값을 빠른 시간 내에 찾을 수가 없다.

2-2-2. B-Tree

B-Tree 는 트리 자료구조의 일종으로 이진트리를 확장해 하나의 노드에 2개 이상의 노드를 가질 수 있습니다.
가장 상단에 있는 노드는 Root노드(=마스터노드), 중간에 있는 노드를 Branch 노드, 하단에 있는 노드를 reaf 노드라고 합니다.

key 값을 이용해 찾고자 하는 데이터를 트리 구조를 이용해 찾는 것입니다.

예를 들어 🎈🎈🎈🎈🎈🎈🎈🎈🎈수정가능성있는부분 ---------

Root(master) node 에 제일큰값과 작은값인 1 과 10 으로 이루어질때

Branch(middle) node 는 Root node에서 보통은 4개~16개로 2의 제곱수만큼 갈라져 나와 →2 , 4,  6, 8  이 되고 

Reaf node는 1~ 10까지 10개로 이루어진다.
이부분 수정 가능성 있음
비트리 삽입 알고리즘 -> 균형트리 -> 이진트리 개념 구글링해보기 
------------

풀 스캔이 테이블의 크기에 비례하는 형태로 실행 시간이 늘어가는데에 비해 인덱스를 사용한 경우 실행 시간의 저하는 보통 원만한 곡선을 그리게 된다.

2-2-3. B+Tree

B+tree는 B-tree의 확장개념으로, B-tree의 경우, branch 노드에 key와 data를 담을 수 있다. 하지만, B+tree의 경우 브랜치 노드에 key만 담아두고, data는 담지 않는다. 오직 리프 노드에만 key와 data를 저장하고, 리프 노드끼리 Linked list로 연결되어 있다.

B+tree의 장점

1. 리프 노드를 제외하고 데이터를 담아두지 않기 때문에 메모리를 더 확보함으로써 더 많은 key들을 수용할 수 있다. 하나의 노드에 더 많은 key들을 담을 수 있기에 트리의 높이는 더 낮아져 검색속도가 빠르다..(cache hit를 높일 수 있음)

2. 풀 스캔 시, B+tree는 리프 노드에 데이터가 모두 있기 때문에 한 번의 선형탐색만 하면 되기 때문에 B-tree에 비해 빠르다. B-tree의 경우에는 모든 노드를 확인해야 한다.

B+tree의 단점

1. B-Tree의 경우 최상의 경우 특정 key를 root node에서 찾을 수 있지만, B+Tree의 경우 반드시 특정 key에 접근하기 위해서는 leaf node까지 가야 하는 단점이 있다.

인덱스에서 B-Tree 대신 주로 B+Tree를 사용하는 이유는 뭘까?

해시 테이블에서 언급했듯이 인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생할 수 있다. 따라서 B+Tree의 Linked list를 이용하면 순차 검색을 효율적으로 할 수 있게 된다.

B+Tree의 검색 과정은 B-Tree와 동일하다. 반면 B+Tree의 삽입과 삭제 과정은 약간의 차이가 있다. 기본적으로 B+Tree의 삽입과 삭제는 항상 leaf node에서 일어난다.

2-3. 인덱스 장점

테이블을 검색하는 속도와 성능이 향상된다. 또 그에 따라 시스템의 전반적인 부하를 줄일 수 있다.
핵심은 인덱스에 의해 데이터들이 정렬된 형태를 갖는다는 것이다. 기존엔 Where문으로 특정 조건의 데이터를 찾기 위해서 테이블의 전체를 조건과 비교해야 하는 '풀 테이블 스캔(Full Table Scan)' 작업이 필요했는데, 인덱스를 이용하면 데이터들이 정렬되어 있기 때문에 조건에 맞는 데이터를 빠르게 찾을 수 있다.

검색 속도 개선

인덱스는 데이터베이스 테이블에서 원하는 데이터를 빠르게 찾을 수 있도록 도와줍니다. 인덱스를 사용하면 전체 테이블을 검색하는 것이 아니라 인덱스를 통해 빠르게 검색할 수 있으므로, 검색 속도가 개선됩니다.

이때 내부적으로는 주로 B-tree알고리즘이 사용되며, 시간복잡도가 O(LogN)이기때문에 인덱스를 사용하지않았을때 O(N)보다 월등히 빠른 속도로 검색이 가능합니다.

쿼리 성능 개선 및 디스크 I/O 비용 감소

인덱스를 사용하면 쿼리 실행 속도 개선 및 디스크 I/O 비용을 줄일 수 있습니다. 인덱스를 사용하면 DBMS가 데이터를 검색할 때 전체 테이블을 스캔하지 않고, 인덱스를 스캔하여 원하는 데이터를 찾을 수 있기 때문입니다.

2-4. 인덱스 단점

인덱스는 반드시 정렬도니 상태로 존재해야하기 때문에 조회쿼리만 사용시에 성능 보장할 수 있지만
삭제 , 수정이 일어날 시 반복적으로 인덱스페이지를 재정렬하여 부하가 걸리므로
인덱스를 사용하기에 적합한 경우인 변경 가능성이 적고 조회가 많이 일어나는 경우 용이합니다.