💡 Database에서 Index란?

인덱스란 “추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를

향상시키기 위한 자료구조”이다. 이러한 인덱스는 자주 사용되는 값으로 만들어진

원본 테이블의 사본이라고 생각할 수 있다.

만약 인덱스를 사용하지 않은 컬럼을 조회해야 하는 상황이라면 전체를 탐색하는 Full Scan을

수행해야 한다. 이 방법은 DB 전체를 비교탐색하기 때문에 처리 속도가 떨어진다.

또한 CREATE, DELETE, UPDATE가 빈번한 속성에 인덱스를 걸게 되면 인덱스의 크기가 비대해져서

성능이 오히려 저하되는 역효과를 발생할 수 있다.

정리해보자면, 인덱스는 “검색”에 최적화된 기능이기 때문에 생성, 삭세, 수정이 자주 일어나는

테이블에서는 사용을 안하는 편이 좋을것 같다.

💡 Index의 동작원리

⒈ Index Table(원본 테이블의 사본)에서 where절에 포함된 값을 찾는다.

⒉ 해당 값의 id 값을 가져온다.

⒊ 가져온 id값으로 원본 테이블에서 값을 조회한다.

아래 사진을 보면 Indexes에 Index Table이 생성된걸 확인 할 수 있다.

예를 들어 쿼리문을 아래와 같이 작성하였을 때

SELECT * FROM table WHRER user_id=”John”

Index가 없는 경우 John이 어떤 블록에 들어 있는지 모르기 때문에 모든 데이터를 db buffer cache로

복사한 후 하나하나 찾는다. 반면 Index가 있는 경우 where절의 컬럼(user_id)의 index가 만들어져 있는지

확인 후, 인덱스에 먼저 가서 John의 정보가 어떤 ROWID를 가지고 있는지 확인한 후 해당 ROWID에 있는

블록만 찾아가서 db buffer cache에 복사한다.

💡 B-Tree

“B-Tree”란 Balanced Tree로 균형을 유지하는 tree를 의미한다.

ORACLE과 같은 사용 DB에서 많이 사용하는 자료구조이며, 외부검색에 유용하다고 알려져 있다.

B-Tree는 이진트리와는 달리 하나의 노드가 여러 데이터를 가질 수 있다.

• B-Tree의 규칙

1. 노드의 데이터 수가 N이면 자식의 수는 항상 N+1이 되어야한다.

2. 노드 내의 데이터는 반드시 정렬된 상태여야 한다.

3. 노드의 데이터 X의 왼쪽 서브 트리는 X보다 작은 값들로 이루어져 있어야하고, 

   X의 오른쪽 서브 트리는 X보다 큰 값들로 이루어져 있어야 한다. 

   > 이진트리의 성질과 유사

💡 B+Tree

“B+Tree”는 B-Tree의 확장개념으로, 리프 노드를 제외하고 데이터를 담아두지 않기 때문에

메모리를 더 확보함으로써 더 많은 key들을 수용할 수 있다.

결과적으로 하나의 노드에 더 많은 key들을 담을 수 있기 때문에 트리의 높이는 더 낮아지며,

cache hit 확률은 더 높일 수 있다.

또한 Full Scan 시, B+tree는 리프 노드에 데이터가 모두 있기 때문에 한 번의 선형탐색만

하면 되기 때문에 B-tree에 비해 빠르다. 반면 B-tree의 경우에는 모든 노드를 확인해야 한다.

리프 노드들은 Linkedlist로 연결되어 있다.

InnoDB 는 B+tree Index 로 이뤄져 있음

📚 References

• Tcp School

• db 성능향상 정리 블로그

• Index 참고 블로그1

• Index 참고 블로그2

• B-Tree 참고 블로그

• B+Tree 참고 블로그