티스토리 뷰
Index의 개념
index란 책의 색인과 비슷한 개념으로서 DB에 있는 데이터를 더욱 빠르게 검색 할 수 있도록 해주는 데이터 구조이다. 책에서 특정 단어를 찾고 싶을 때 처음부터 끝까지 정독하면서 찾아야 하는 것을 색인 이라는 도구를 이용해 쉽고 빠르게 찾을 수 있는 것처럼, 특정 데이터를 찾고 싶을 때 index를 통해 더욱 빠르게 찾을 수 있게 된다.
SQL을 통해 만든 DB에 name과 age가 있는 테이블이 있다고 가정해보자. 이 때 age에는 1억개의 값이 있고 age가 20인 행을 찾고자 한다면 1행부터 1억행 까지 20이 나올 때까지 탐색을 해야할 것이다.
이 때 index를 사용하면 훨씬 더 빠르고 쉽게 찾아낼 수 있게 된다. index는 기존 테이블에 있는 열의 값을 따로 빼내서 값을 정렬을 해놓기 때문에, 특정 열의 값을 index로 만들어 놓으면 이를 탐색하고자 할 때 이미 정렬이 되어 있기 때문에 더욱 빠르게 찾을 수 있게 되는 것이다.
index가 어떻게 더욱 빠른 탐색을 지원하게 되는지에 대해서는 index의 데이터 저장 방식에 대해 알게 되면 이해가 쉬울 것이다. 아래 그림을 보자.
index의 데이터 저장 방식은 다양한데, 그 중 대표적인 'Binary Search Tree'의 형태를 예시로 들어서 설명하고자 한다. 위 그림처럼 트리의 형태로 정렬이 되어 저장이 되기 때문에 탐색하고자 하는 값을 처음부터 끝까지 일일이 찾아볼 필요가 없어진다.
처음 예시처럼 age 20을 탐색하게 되면 루트 노드에 있는 50을 찾아가서 20을 대입시켜 더 큰지, 작은지를 판별하게 된다. 더 작으므로 왼쪽 30을 찾아가게 되고 30을 기준으로 20 보다 더 큰지, 작은지를 판별하게 된다. 더 작으므로 자식 노드 중 왼쪽 노드인 20을 찾아서 출력을 하게 된다.
index를 사용하지 않았을 때는 20을 찾기 위해 처음부터 끝까지 탐색을 해야 했지만, index를 사용함으로써 더욱 빠르고 쉽게 탐색을 할 수 있게 되었다.
위의 예시처럼 'Binary Search Tree'를 사용해서 정렬할 수도 있지만, 실제로는 'B-Tree' 혹은 'B+Tree'의 형태로 저장하는 경우가 많다. 이는 'Binary Search Tree'의 기본 형태를 따르지만 약간 변형된 형태로서 더욱 효율적으로 탐색을 할 수 있게 해준다.
*참고로 index를 만들게 되면 index를 만든 테이블의 열에 연결이 되어서 만들어진다. 즉 index를 통해 원하는 데이터를 찾으면 그 데이터에 연결되어 있는 테이블의 행을 찾아가서 그 행을 출력하게 되는 것이다.
B-Tree와 B+Tree
B-Tree
위 트리는 B-Tree의 예시이다.
"Binary Search Tree"와는 달리 여러 노드 값을 넣어놓고 크기를 비교해서 탐색을 하게 된다.
예를 들어서 11을 탐색하게 되면 먼저 루트 노드에 접근하게 되는데 7보다 크고 13보다는 작으므로 11, 12가 함께 있는 노드로 이동하게 되면서 11을 찾게 된다.
만약 14을 탐색하게 되면 13보다 크고 17 보다는 작으므로 14, 16이 함께 있는 노드로 이동하게 되면서 14를 찾게 된다.
"Binary Search Tree" 보다 더 빠르고 쉽게 데이터를 탐색할 수 있게 된 것이다.
B+Tree
위는 B+Tree의 예시이다.
B+Tree는 B-Tree와 비슷하지만 차이점 몇가지가 존재한다.
*차이점
1. B-Tree의 경우 각 노드에 실제 데이터 값이 저장되어 있는 반면 B+Tree의 모든 데이터는 '리프 노드'에 저장이 되어 있다. 리프 노드 외의 상위 노드들에는 리프 노드의 위치가 담긴 '가이드'가 저장되어 있다.
즉 그림에 있는 상위 노드들의 값인 7, 16, 5, 11, 22, 45는 실제 데이터가 저장되어 있는 것이 아닌 일종의 키 값으로서 리프 노드에 있는 값을 찾아가기 위해 존재하는 가이드일 뿐이라는 것이다.
예를 들어 4를 찾고자 한다면, 먼저 7, 26 노드를 찾아가는데 해당 노드에는 '7보다 작으면 왼쪽으로 가라' 라는 가이드가 적혀 있다. 그럼 하위 노드로 가서 5 노드를 찾아가게 되는데 해당 노드에는 '5보다 작으면 왼쪽으로 가라' 라는 가이드가 적혀 있다. 그럼 왼쪽으로 가서 4를 찾게 되는 것이다.
2. 리프 노드에는 포인터가 존재한다. 고로 범위 탐색에 유리하다. 만약 4~7까지의 데이터를 찾고 싶으면 4를 기준으로 해서 7 이하니깐 왼쪽 -> 5 이하니깐 왼쪽으로 가서 4를 찾은 뒤 화살표를 따라 7까지 그냥 옆으로 이동해서 찾으면 된다.
(이러한 장점 때문에 요새는 B+TREE 구조를 많이 이용한다.)
Index 주의 사항 및 단점
*탐색이 필요없는 데이터의 경우에는 따로 index를 만들게 되면 오히려 쓸데없이 용량만 더 차지하게 되기 때문에 지양하는게 좋다.
*primary key의 경우 알아서 정렬이 되기에 따로 index를 만들어 줄 필요가 없다.
*단점
-index를 만들게 되면 DB의 용량을 추가로 사용하기 때문에 용량 차지하는 문제가 있다.
-기존 테이블의 데이터를 CRUD 했을 때 index에도 똑같이 계속 일일이 반영을 해줘야 하는 문제가 있다.
=> 하지만 여러 단점을 상쇄 할만큼 사용했을 때의 장점이 크다.
'기술 노트' 카테고리의 다른 글
| 쿠키와 세션, OAuth, JWT에 대하여 (0) | 2023.04.29 |
|---|---|
| Node.js의 '특징'과 '동작원리' 그리고 JS의 '동작원리' (0) | 2023.04.08 |
| 컴퓨터의 구조와 OS의 관계 (0) | 2023.03.21 |
| defer과 async를 통해 HTML과 JS를 연결하기. (0) | 2023.03.19 |
| 모듈을 Import 할 때 { }(중괄호)를 쓰는 경우와 아닌 경우(Node.js) (0) | 2023.03.15 |