[IT_Infra] 탐색알고리즘(Searching) - 트리(Tree)(인덱스), 해시(Hash)

탐색알고리즘(Searching) - 트리(Tree)(인덱스), 해시(Hash)

1. 탐색 알고리즘?

- 데이터 구조 : 데이터를 정리 방법

- 데이터 검색 : 탐색 알고리즘

1) 예    

- 영한 사전은 알파벳 순(데이터구조)으로 구성, 알파벳으로 찾기(탐색알고리즘)를 한다

2. 사용되는 곳

1) DBMS

 SQL 튜닝 시에 풀 스캔으로 돼 있어서 느렸는데, 인덱스를 생성해서 인덱스 스캔하니 빨라졌다?

- 반드시 인덱스가 빠른것은 아니다, 풀 스캔이 빠른 경우도 있다

A. 인덱스가 없을 때

- 디스크에서 테이블 데이터를 모두 읽어서 조사해야한다

- 모든 블록을 처음부터 순서대로 읽음(FULL-SCAN)

- 테이블 크기가 커질 수록 블록도 많아짐

B. 인덱스 있을 때

- 일반 적으로 B 트리 인덱스(트리 구조 계층이 깊어 지지않기 때문에:줄기가 많다)) 사용

- 최소한의 필요 블록만 읽으면 된다

- 검색이 빨라지는 대신 데이터 추가, 갱신, 삭제 시에 테이블 뿐만 아니라 인덱스 데이터도 갱신해야한다(오버헤드 발생)

(서류철을 정리할 때 인덱스 스티커를 붙여두면 빠르게 찾지만, 대신 서류를 추가 할 때는 인덱스를 수정해야함)

C. 인덱스 구조

SELECT * FROM EMP WHERE EMPNO = 7369

1. SQL이 발행되면 루트 블록을 본다

2. 브랜치블록1에 있다는 것을 안다

3. 브랜치 블록1을 보면 리프 블록1에 있다는 것을안다

4. 리프블록1을 보면 데이터 블록 어디에 데이터가 저장되어 있는지 안다

D. 인덱스를 잘못 사용하면?

- 인덱스는 읽을 블록 수를 줄이기 위한 수단이지만, 오히려 읽을 블록 수가 늘어 날 수 있다

예) 테이블 데이터를 모두 취득해야 하는 경우

- 테이블의 모든 블록뿐만 아니라 인덱스 블록까지 읽어야 하기 때문에 디스크 I/O증가한다

- 책을 처음 부터 다 읽어야 하는데 인덱스를 보면서 처음부터 읽는 것과 같다

2) 해시 테이블

- 키와 값 조합으로 표를 구성한 데이터 구성

- 등호 검색에 강하다, 범위 검색에 약함

1) 키

- 키는 해시 함수를 통해 해시 값으로 변환

2) 값

- 해시 값은 고정 길이 데이터이기 때문에 조합 표의 데이터 구조가 간단해서 검색이 빠르다