인덱스, 페이지

보통 해시 테이블, b 트리로 구현되는 쿼리가 나갔을때 테이블의 검색 속도를 향상시키는 방법(자료구조).

 

인덱스 관리

인덱스가 적용된 컬럼에 insert, update, delete 를 수행하면 다음과 같은 연산을 추가적으로 해줘야 한다.

- insert : 새로운 데이터에 대한 인덱스 추가 

- delete : 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업 진행

- update : 기존 인덱스 사용하지 않음 처리, 갱신된 데이터에 대한 인덱스 추가 

 

update, delete 시 기존 인덱스를 지우는게 아닌, 기존 인덱스를 '사용하지 않음 처리' 한다.

 

 

장단점

당연히 검색 속도가 빨라진다.

하지만 인덱스를 위한 추가 저장공간 (약 10%)가 필요하고, 

인덱스를 만들고 갱신하는데 추가 작업이 필요하게 되므로 잘못 쓰게되면 오히려 성능이 저하할수 있다.

 

update, delete 시 기존 인덱스를 지우는게 아닌, 기존 인덱스를 '사용하지 않음 처리' 하기 때문에 update, delete 가 자주 일어나는 속성에 인덱스를 걸면 인덱스가 계속해서 쌓인다.

 

 

인덱스를 사용하면 좋은 경우 

- 규모가 큰 테이블

 

- insert, update, delete 가 자주 발생하지 않는 컬럼 

 

- join, where, order by 에 자주 사용되는 컬럼

 위 연산의 경우 당연히 컬럼 조회를 해야하기 때문에 인덱싱되어 있으면 빠르다.

 insert, update, delete 와 다른점은 이것들은 인덱스 생성 및 수정하는데 추가 오버헤드가 필요하기 때문이다.

order by 는 정렬인데, 정렬 위해서는 당연히 조회를 해야하기 때문에 조회가 빨라지면 정렬도 빨라진다.

얘내들은 예를들어 인덱스가 b tree 로 구현되어 있다면 트리 구조가 바뀌지 않는 연산들이다.

 

페이지

dbms 에서는 I/O 는 페이지(블록) 단위로 이루어진다. (dbms 의 기본 저장 I/O 단위) 

하나의 레코드를 읽더라도 레코드가 속한 블록 전체를 읽는다. 

 

 

인덱스의 구조 

해시 테이블 

(key,value) 로 (컬럼값, 데이터 주소) 를 사용한다.

 

해시 테이블의 검색 속도는 O(1) 이기 때문에 매우 빠르다.

 

하지만 잘 사용하지 않는데 이유는 해시가 (=) 등호 연산에만 특화되었기 때문에 부등호 연산이 자주 사용되는 데이터베이스 검색에 적합하지 않다.

예를들어 "나는" 으로 시작되는 모든 데이터를 검색하기 위한 쿼리는 이에 부적합하다.

 

B-트리

https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-B-Tree

[자료구조] 그림으로 알아보는 B-Tree

자식을 두개만 갖는 이진트리를 확장하여 여러개의 자식 노드를 갖을수 있다.

B트리는 이진트리와 다르게 하나의 노드에 여러개의 값을 갖을수 있다.

이진트리처럼 부모노드의의 왼쪽 자식들은 항상 부모노드보다 작고, 오른쪽 자식들은 부모 노드 보다 크다.

루트부터 대소관계를 비교해서 찾는 값이 어떤 key 들의 사이에 있다면 해당 key 들 사이의 자식 노드로 간다.

검색 : 예를들어 15를 찾는다. 루트부터 시작하면 10과 20 사이기 때문에 14,17 key 를 갖는 노드로 이동한다.

 

삽입 : 1. 요소 삽입에 적절한 리프 노드 검색. 2. 필요한 경우 노드 분할.

분할이란 요소 삽입에 적절한 리프 노드를 찾았는데 노드의 최대 key 수를 초과했을때 발생한다.

해당 노드의 중앙값을 부모노드에 오름차순으로 삽입하고, 분할한 두개의 노드를 왼쪽, 오른쪽 자식으로 설정한다.

key 갯수가 초과되는 노드가 없을때까지 반복한다.

 

 

 

B+ 트리

https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-B-Plus-Tree

[자료구조] 그림으로 알아보는 B+Tree

 

 

 

- 모든 key, data 가 리프노드에 있다.

 

- 모든 리프노드가 연결리스트다. 

 즉 리프노드가 연결리스트이기 때문에 선형검색이 가능하다. 

 

- 리프노드의 부모 키는 리프노드의 첫번째 키보다 작거나 같다. 

 

- db 의 인덱스 컬럼은 부등호에 의한 순차 검색 연산이 자주 발생할수 있다(ex. "ab"  로 시작하는 모든 데이터 검색).

따라서 B-Tree 의 리프 노드들을 연결리스트로 연결하여 순차검색이 가능한 B+ 트리가 적합하다.

 

- 데이터가 모두 리프노드에 있기 때문에 검색 시간복잡도 O(logN)