index (색인)

tahn·2022년 11월 24일
0

CS_Study

목록 보기
2/4

인덱스란?

인덱스를 번역하면 “색인”이라는 뜻을 가지고 있다.

1. 어떤 것을 뒤져서 찾아내거나 필요한 정보를 밝힘

2. 책 속의 내용중에서 중요한 단어나 항목, 인명 따위를 쉽게 찾아볼 수 있도록 
일정한 순서에 따라 별도로 배열하여 놓은 목록

3. 책 송게 다루어진 중요한 단어나 용어를 독자가 쉽게 찾을 수 있도록 페이지를
밝혀 벌여 놓은 것. 

즉 색인 이란 책의 “목차”다.

내가 엄청 두꺼운 1000page의 책에서 정보를 찾아야 된다고 가정해보자. 목차가 있다면 목차를 살펴보고 내가 원하는 페이지에 이동해서 필요한 정보를 찾을 수 있다. 하지만 목차가 없다면 일일이 모든 페이지를 넘겨가면서 정보를 찾아야 하는 일이 발생한다.(DB에서는 이런 일을 Full Scan이라고 함)

이렇게 되면 엄청난 시간 소모와 자원이 낭비된다.

데이터 베이스에서는 이를 방지하기 위해 책의 목차와 같은 기능인 INDEX(인덱스)라는 것이 존재한다.

DB에서의 인덱스

DB에서의 인덱스는 RDMS에서 검색 속도를 높이기 위한 기술이다.

즉 테이블 칼럼을 색인화 하는 것이다.

칼럼을 색인화 하면 INDEX 파일 검색을 통해 속도를 향상시킬 수 있다.

그러나 INSERT, UPDATE, DELETE의 경우 인덱싱을 하면 정렬된 상태를 유지해야 하고, 테이블 외에 인덱스 테이블에도 INSERT, UPDATE를 해줘야 하기 때문에 속도는 더 느려진다.

그렇기 때문에 인덱스는 변경보다 검색이 많을 경우에 사용하면 더 효율적이라는 것을 알 수 있다.

(+ Private Key와 Unique 설정 시 자동으로 인덱스가 생성된다.)

B-Tree와, Hash 인덱스 알고리즘

B+-Tree 인덱스 알고리즘

일반적으로 사용되는 인덱스 알고리즘은 B+-Tree 알고리즘이다. B+-Tree 인덱스는 칼럼의 값을 변형하지 않고(사실 값의 앞부분만 잘라서 관리한다.), 원래의 값을 이용해 인덱싱하는 알고리즘이다.

Hash 인덱스 알고리즘

칼럼의 값으로 해시 값을 계산해서 인덱싱하는 알고리즘으로 매우 빠른 검색을 지원한다. 하지만 값을 변형해서 인덱싱하므로, 특정 문자로 시작하는 값으로 검색을 하는 전방 일치와 같이 값의 일부만으로 검색하고자 할 때는 해시 인덱스를 사용할 수 없다. 주로 메모리 기반의 데이터베이스에서 많이 사용한다.

왜 index를 생성하는데 b-tree 를 사용하는가?

데이터에 접근하는 시간복잡도가 O(1)인 hash table 이 더 효율적일 것 같은데? SELECT 질의의 조건에는 부등호(<>) 연산도 포함이 된다. hash table을 사용하게 된다면 등호(=) 연산이 아닌 부등호 연산의 경우에 문제가 발생한다. 동등 연산(=)에 특화된 hashtable은 데이터베이스의 자료구조로 적합하지 않다.

참고한 레퍼런스

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/Database#index

profile
html 개발자

0개의 댓글