1. 들어가기전...
들어가기에 일단 사용하는 용어부터 혼동을 위해 미리 말해둘것이 있다.
참고로 네이버 사전을 이용해 index를 검색해 보면 아래와 같이 번역되어 있는데
"인덱스"를 번역한게 "색인"이다
그런데, "인덱스"와 "색인"을 둘 다 섞어서 사용한다.
앙드레김 선생님도 아닌데 왜 영어랑 해석된 단어랑 섞어쓰는거지? 라고 할지 모르겠는데 편의상 아래와 같이 구분해서 쓰도록 하겠다.
"색인" (=indexing)
1. 인덱스를 만드는 과정이나 행위를 의미함.
"인덱스" (=index)
1. 색인하여 만들어진 결과물.
2. 색인과 인덱스
"오늘은 5월 20 이죠? 바로 '세계인의 날' 입니다"
주말근무를 하던 선배는 라디오를 듣다가 깜짝놀라며 말했다. "뭐 오늘이 색인이 날이라고?"
색인이 뭔데 이런 반응이 나오는걸까? 색인은 검색을 빠르게 하기위한 필수 과정이다.
색인이란게 어떤건지 이해할수 있도록 단계별로 비유를 들어 보겠다.
2.1. 주요단어를 미리 메모장에 적는 단계
책을 보다가 중요한 내용같은건 책갈피를 껴놓거나, 몇페이지인지 적어놓은적이 있는가?
찾으려는 값과 page만 정리를 해 놓으면, 책을 처음부터 보지 않아도 바로 찾아갈 수 있다.
예를 들어 '노들역'이라는 단어가 '54페이지'에 있다고 수첩에 적어두었다고 하자.
여기서 색인이란? 수첩에 정리하는것
여기서 인덱스란? 수첩
여기서 색인어란? 노들역
여기서 ROWID란? 54페이지
여기까지 설명을 듣고, " 우와 쩐다. 모든 단어를 쉽게 찾을 수 있도록 모조리 수첩에 적어야지"
이러는 사람이 있을지 모르겠다. 하지만 수첩에 모든 단어를 정리하는건, 책 전체를 옮겨 적는수준이다.
당연히 수첩의 두께는 책이랑 비슷하고 책에서 찾나 수첩에서 찾나 도토리 키재기 일 것이다.
이런건 뭐랄까... "밥하기 귀찮아서 라면 먹자고 해놓고, 라면먹고 밥말아 먹자며 밥 짓는 꼴이랄까?"
2.2. 인덱스를 빨리 찾는 방법들
사실 위에서는 문제점을 언급하기 위해 이야기 안했지만, 인덱스를 빨리 찾는 방법이 있다.
Hash라는 기법과 이진검색 같은 방법이다. 사실 우리는 이런 방법을 생활에서 나도 모르게 쓰고 있다.
이진검색?
소주뚜껑에 써있는 숫자를 찾는 게임을 아는가?
1~35 사이에서 찾는다고 하면 적힌 숫자를 맞추는 게임이다 (맞추면 벌주를 먹지만...)
아무튼, 우리는 여기서 자연스럽게 이진탐색 기법을 사용 하고 있다.
숫자의 반, 또 그 반 , 그반 이런식으로 접근하는 방식을 말한다.
예를 들어, 1~35라는 숫자에서 찾는다면?? (답은 23이라고 하자)
(1) 17 -- up (1~35)
(2) 25 -- down (18~35)
(3) 21 -- up (18~24)
(4) 23 -- 빙고! (22~24)
기냥 무식하게 1~35를 차례대로 가면 최악의 경우 35번째 사람이 걸리지만
이 방법을 쓰면 5번 정도면 찾을수 있다.
이때 핵심은 정렬(sort) 되어있어야 한다는것이다. <== 잊지말자 ^^
값자체를 찾을수 있는 특별한 함수(해쉬함수 or 해쉬펑션)를 쓰는것이다.
예를 들어 전화번호부에서, ㄱ ㄴ ㄷ 로 분류를 해놨다.
이런것도 일종의 해쉬를 사용했다고 볼 수 있다.
전화번호부의 해쉬함수는 앞글자의 초성만 뽑는 함수라고 할 수 있다.
* 해쉬함수("고길동") =return==> ㄱ
* 해쉬함수("홍길동") =return==> ㅎ
* 해쉬함수("황장미") =return==> ㅎ
전화번호부가 240페이지라고 치면, 홍길동을 찾을때 'ㅎ' 에서만 찾으면 되고 초성은 24개니까 240페이지/24개 = 10, 즉 10페이지만 찾아보면 된다.
그런데, 홍길동과 황장미의 해쉬값은 'ㅎ' 으로 같아서 중복된다. 이런걸 해쉬충돌이라고 한다.
사실 더 생각해 보면 우리나라는 김씨가 많으니 ㄱ에 해쉬충돌이 많이 나서, 균등하게 24등분 되지는 않을것이다. 이런 문제를 고려해서 해쉬함수는 충돌을 줄이도록 만들어야 한다.
좀 더 알고싶다면 검색하거나 읽어보자. => http://dblab.duksung.ac.kr/ds/pdf/Chap13.pdf
3. 인덱스를 사용하지 못하는 문제 (full scan)
인덱스를 쓰면 위에서 설명한 방식을 통해 빠른 검색을 할 수 있고, 부수적으로 일부 데이터만 읽으면되기 때문에 IO를 줄일수 있어서 더 효율이 높아진다. 컴퓨터에서 IO가 엄청 느리다는것은 아마 전산학도라면 누구나 알고 있는 것이라 자세한 설명은 생략한다.
아무튼, 완전 멋지지 않은가? 그런데 인덱스를 못쓰는 경우가 발생한다.
인덱스는 해당 값과 같은값을 찾거나(exact검색), 범위의 값(숫자나 날짜)만 사용이 가능하다.
인덱스를 못쓰고 전체를 뒤져야 하는 경우를 풀스캔(FULL SACN)이라고 한다.
DB에서는 풀스캔을 하는경우 인덱스가 없거나, 일부 like검색에서 나타난다.
여기서 심심해할 독자를 위한 질문 title필드에 인덱스를 걸었다고 치면 어떤게 인덱스를 못쓸까?
a) select * from table where title ='맛집';
b) select * from table where title like '%맛집%';
c) select * from table where title like '맛집%';
d) select * from table where title like '%맛집';
답은 (b) (d) ... 왜 b와 d는 인덱스를 못쓸까?
B트리, B-트리, B+트리
우선 인덱스의 구조를 알아야 겠다. 위에서 이진검색을 이야기 했는데 사실 더 발전된 B트리라는걸 사용한다.
예를 들어, 63이라는 값을 찾는다고하면 트리의 맨위 즉 ROOT에서 시작한다.
root는 [8,14,37,52] 63은 52보다 크기 때문에 오른쪽 노드로 내려간다.
그러면 [53,61,64,72] 63은 61보다 크고 64보다 작다. 두 노드의 사이로 내려간다
[61,63] 63은 61보다 크고 하위노드가 없다. 찾았다!!!!
(문자열은 숫자가 아닌데 크고 작고가 어딧냐고 묻는다면. 디지털세상은 0과 1... 2진수라는걸 잊지말자)
좌절단, 좌우절단은 인덱스를 못쓴다.
다시 (b)(d)가 인덱스를 못쓰는 이유로 돌아와 보자. 문자열의 검색에서는 like 검색, 즉 절단검색을 쓴다.
(b)는 양쪽다 잘렸다고 해서 좌우절단, (d)는 왼쪽이 잘렸다고 해서 좌절단이다.
좌절단이 있으면 인덱스를 못쓴다
트리를 만드는 가장 핵심은 정렬이다. 정렬된값을 비교할때는 앞 글자부터 비교한다. (앞글자 => 왼쪽글자)
좌절단은 시작값을 모른기 때문에 트리의 탐색을 할 수 없다.
예를 들면, 전화번호부에서 성을 모른채로 "길동"이를 찾는것이다.
성을 모르니, ㄱ~ㅎ 을 모두 뒤져야 한다.(고길동 부터 홍길동)
exact, 우절단은 인덱스를 쓸수 있다.
일치하는값...즉 equals를 exact라고 하고, 오른쪽이 잘린조건을 우절단이라고 한다.
exact검색은 인덱스 쓰는걸 알겠는데 우절단은 왜 ??
우절단이 검색이 인덱스 가능한 이유는 맨앞쪽글자는 있으니 트리를 일부 탐색할 수 있다는것이다.
(아래 트리는 발로 그린거라 밸런스가 그런거 무시했다... 따지지 말자 ㅋㅋ)
맨앞 글자가 존재하니 root에서 다음노드를 찾을수 있다.
root는 [나라, 사람, 장난감, 화장실] "맛집"은 '장난감' 과 '화장실' 사이노드..
그럼 [라면, 맛집] 가 있고, "맛집"이라는 값을 찾았고 그 하위 노트 통째가 결과로 쓸수 있다.
예를 들면, 전화번호부에서 이름은 상관없이 '홍' 씨 찾기 이다. 이때는 전체를 뒤지지 않고 'ㅎ' 영역에서 홍씨만 찾으면 된다. 즉 인덱스를 사용할 수 있다는것이다.
4. 마치며
이제는 검색을 빨리하는 비밀인 색인이라는 것을 어렴풋이 알게 되었다.
사실 위에서 사용하는 방식은 DBMS에서 인덱스를 만들때 이미 사용하는 방식이다.
그런데, 왜 검색엔진을 도입하는것일까?
사실, DB에서는 지원하지 않거나 지원이 약한 색인기술이 검색엔진에 존재한다.
형태소분석기, NGRAM, Stemming, 문자열의 필드타입들등등...
2부는 이야기할 내용이 많아서 여기서 일단 쉬어가고, 2부 2편에서 계속 글을 이어가겠다.