용어정리
우선 용어부터 알고가자
컴퓨터에서 정보를 저장하는 장치는 메인 메모리(RAM), 하드디스크(HDD)등이 있다.
메모리
- 주기억장치, 메인 메모리, 메모리, RAM 다 같은 용어
- 전기신호로 정보를 저장하기에 속도가 매우 빠름.
- 휘발성 기억장치, 전원끄면 내용이 다 날아감.
하드디스크
- HDD, 보조기억장치
- 물리적으로 정보를 저장하기에 속도가 느림
- 비휘발성
DB 인덱스
더 빠른 검색을 위해 특정 컬럼에 대하여 정렬하여 색인을 만들어 데이터의 저장위치를 빠르게 찾을 수 있도록 하는 것
디스크 접근 횟수 줄이기
하드디스크는 암(Arm)을 트랙위로 이동하여 데이터를 읽어오는데 이때 한번에 불러올 수 있는 양이 블럭이다.
하드디스크에 접근해 데이터를 불러오는 시간은 메인메모리 작동시간에 비해 매우매우 크기때문에 최대한 디스크 접근 횟수를 줄이는 것이 필요하다.
이진탐색트리계열의 경우 내장탐색트리로서, 메모리에 올려놓고 사용하기에 디스크 접근횟수를 고려하지 않아도 되지만
데이터의 양이 매우 크다면 디스크에 저장해야한다.
디스크 접근횟수를 줄인다는 것은 노드의 접근횟수를 줄이는 것이고, 이는 트리의 높이를 줄인다는 것과 같다.
트리의 높이를 줄이기위해선 어떻게 해야할까? 한 노드에 여러 key를 저장하면 된다. 한 노드에 여러 key를 저장하고 균형적인 트리구조를 유지해 트리의 깊이를 줄여 노드 접근횟수를 줄이고, 최종적으로 디스크 접근횟수를 줄이는 것이다.
따라서 한 노드에 들어가는 데이터양을 디스크에서 한번에 불러올 수 있는 한 블럭의 양과 비슷하게 설정하고, 한 노드당 한번의 디스크 접근으로 해결할 수 있도록 한다.
따라서 b-tree구조를 대용량 정보를 저장하는 DB에 많이 사용하는 것이다.
그런데 다른 데이터 구조는 DB에 사용할 수 없는 것일까?
해시구조
실제로 DB에서 해시구조를 인덱스로 사용하는 특정 경우도 있다. 하지만 보편적으로 사용하지 않는 이유는 해시구조는 '='연산에만 유리하다.
(key, 저장 위치)로 저장한다고 할 때,
'1': 1 위치
'2': 2 위치
'3': 3 위치 이런식으로 저장된다.
즉 '3'이란 키를 찾을 때에는 O(1) 시간이 들지만, 3보다 작은 키를 찾으려면 최악의 경우 모든 데이터를 찾아야해서 O(n) 시간이 드는 것이다.
균형잡힌 이진트리
그냥 이진 트리는 최악의 경우(균형이 잡히지 않아 계속 선형탐색을 하게되는 경우) O(N)시간이 든다.
그렇기에 균형잡힌 이진트리인 AVL트리, R-B트리 등이 존재한다.
이들의 복잡도도 O(logN)을 보장한다. 그런데 왜 같은 시간복잡도인데도 사용하지 않을까?
위의 시간복잡도란 디스크 접근을 고려하지 않은 단순한 수리적인 계산이기 때문이다. 메인메모리상에서 작동하는 경우엔 위의 복잡도를 가질 것이다.
하지만 이진트리계열은 하나의 노드에 정보를 가져야하기에 데이터의 수가 많을수록 깊이가 깊어질 수 밖에 없다. 이는 디스크 접근횟수를 늘린다.
또한 b-tree에서 같은 노드에 저장된 데이터는 포인터가 필요없이 실제로 물리적으로 저장된 순서와 인덱스상의 위치가 동일하다. 따라서 한 노드에 많은 데이터를 저장하면 속도가 빨라질 수 있다.
반면 이진트리의 경우 참조 포인터를 따라가서 데이터를 찾아야하므로 시간이 오래걸린다.
선형리스트
그렇다면 선형리스트 형식은 어떨까
선형리스트는 자료의 형태가 곧 물리적 저장위치와 같다. 등호 검색, 부등호 검색 모두 잘될 것이다.
하지만 검색시 유리한 것이고, 삽입/삭제시 한 요소를 삭제하거나 삽입할 경우 나머지 자료의 위치를 모두 옮겨야하므로 O(N)의 시간이 들게 된다.
Linked list
linked list는 삽입/삭제시 포인터의 내용만 바꿔주면 되기에 유리한 면이 있지만 검색 시 처음 노드부터 타고 타고 들어가 원하는 key를 찾아야하기때문에 검색에 용이하지 않다.
