데이터베이스의 탐색 성능을 좌우하는 인덱스.
인덱스를 사용하는 이유?
대부분의 속도 저하는 바로 Select문 특히 조건 검색 Where절에서 발생하는데 가장 먼저 생각해 볼 수 있는 대안으로 Index가 존재
그렇다면 왜 B-Tree자료구조를 사용할까?
먼저 자료구조에서 트리란 무엇인가에 대하여 알아보자.
Tree는 평균적으로 시간 복잡도 O(logN)을 가진다.
하지만 최악의 경우
한 쪽으로 쏠려버린 트리다 최악의 탐색 시간 O(N)을 가지게 되어버린다.
이걸 방지하기 위해 밸런스 트리(Balanced Tree)를 이용하기도 한다.
밸런스 트리(Balanced Tree)란?
트리의 노드가 한 방향으로 쏠리지 않도록,
노드 삽입 및 삭제 시 특정 규칙에 맞게 재정렬되어 왼쪽과 오른쪽 자식 양쪽 수의 밸런스를 유지하는 트리
항사 양쪽 자식의 밸런스를 유지하므로, 무조건 O(logN) 시간 복잡도를 가진다
하지만... 노드 삽입 시 삭제 시 발생하는 재정렬 작업 때문에 탐색을 제외한 작업에서는 일반 Tree보다 성능이 저하된다.
위에서 보듯이 밸런스 트리는 최악의 경우에도 O(logN)이므로 인덱스는 밸런스 트리, 그중 B-Tree를 선택했다!
여기서 생각할 수 있는 경우가 많은데
예를 들어 왜 B-Tree일까
데이터구조에서 B-Tree는 들어봤지만 잘 모르고 지나갔다 하지만 하나 기억나는 트리가 있는데
바로 RedBlack-Tree이다 규칙도 신기하고 해서 기억이 난다
자 그러면 왜 B-Tree인가 시간 복잡도로만 따지면 훨씬 빠른 자료구조들이 많다.
그럼에도 불구하고 왜 B-Tree인지 알아보자
1. 해시 테이블은 어떤가?
해시 테이블의 시간 복잡도는 평균적으로 O(1)이다.
하지만 우리는 이걸 인덱스에 적용할 수 없다
왜? 해쉬 테이블은 Keys를 이용해 데이터를 찾을 경우 하나의 데이터 밖에 찾을 수 없다
여기서 중요한 점은 인덱스는 정렬된 데이터란 것이다 해쉬 테이블로 찾는건 부등호로 따지면 == 같을 때다 우리는 크거나 작은 >, < 값들을 찾을 수 없다
하지만 해쉬 테이블로 정렬을 한다? 말이 되지 않는다 해쉬 테이블을 정렬하는 작업들.. 그걸 할 수 있다면 해쉬테이블이 아니라고 볼 수 있기 때문이다
2. 밸런스 트리중 RedBlack-Tree
각 노드의 하나의 값만 가징 상태 좌, 우 자식 노드의 개수 밸런스를 맞춘다
지금 우리는 RedBlack-Tree가 무엇인지 그렇게 깊이 알려고 하는 것이 아니기 때문에 빨간색은 신경쓰지 않아도 된다
그렇다면 RedBalck-Tree와 B-Tree의 차이가 무엇일까?
먼저 B-Tree의 특징으로는
각 노드 내 데이터들은 항상 정렬된 상태이며, 데이터와 데이터 사이의 범위를 이용하여 자식 노드를 가진다.
그러므로 자식 노드 개수는 (n+1)을 가진다
그래서 최악의 경우에도 무조건 탐색 시간이 O(logN)을 가진다.
그러면 밸런스 트리중 어떠한 것도 상관없이 인덱스로 쓸 수 있지 않나?라는 의문이 생기지만
조금만 더 알아보자
사진을 보면 가장 큰 차이는 하나의 노드가 가지는 데이터 개수이다
RedBlack-Tree는 무조건 하나의 노드에 하나의 데이터 요소만을, B-Tree 하나의 노드에 여러 개의 데이터 요소를 저장한다.
표시한 부분을 보면 마치 배열처럼 정리되어있다.
위 표시한 부분은 배열이 맞다.
실제 메모리 상에 차례대로 저장이 되어 있어서 같은 노드 공간의 데이터들끼리 굳이 자식 노드처럼
참조 포인터로 값으로 접근할 필요가 없다!!!
즉 노드 상 데이터를 탐색할 때는 포인터 접근을 하는 것이 아니라
실제 메모리 디스크에서 바로 다음 인덱스로 접근하는 것이다
그래서 RedBalck-Tree는 시간 복잡도가 O(logN)이고 B-Tree도 O(logN)이지만
B-Tree를 사용하는 것이다 B-Tree가 참조 포인터로 접근할 경우가 현저히 적기 때문에 더 빠를 수밖에 없다
왜냐면 참조 포인터로 메모리에 접근을 하는 것 실제 메모리 상으로 접근하는 것은 속도에 유의미한 차이를 낸다.
참조 포인터는 주소를 알아내려고 CPU내부적으로 많은 연산을 수행하게 될 것이기 때문에!
3. 배열을 사용해볼까?
배열은 참조 포인터로 접근하는 것이 아니라 차례대로 메모리상에 저장되어 있기 때문에 속도는 당연히 빠르다
하지만 B-Tree보다 빠른 것은 탐색뿐이다
배열을 잘 알고 있는 사람이라면
배열에서 데이터 저장과, 삭제를 하는 순간을 상상해보자
삭제하고자 하는 배열의 [n]까지 배열이 돌아야 한다.. 이 얼마나 무식한 일인가?
삽입도 마찬가지다 위에 그림처럼 3을 삽입한다면 한칸 한칸 뒤로 미뤄줘야한다.. 그 시간복잡도는 어떻게 할 것인가?
이처럼 배열은 index에 맞지 않다는 것을 알았다
4. 배열이 삽입, 삭제에서 느리다면 LinkedList는?
LinkedList는 삽입, 삭제 시, 중간의 포인터를 잠깐 끊고, 추가될 요소 혹은 삭제할 요소를 처리한 다음, 다시 포인터로 연결만 하면 되기 때문에 배열에서 가지고 있던 삽입,삭제 문제를 한번에 해결할 수 있다.
LinkedList의 특징은 무엇인가? 바로 Head부터 시작하는 특징이있다
탐색을 무조건 제일 앞 부분부터 시작하는 것이다 그렇다면 우리가 원하는 정렬을 하기 어렵다
우리는 이진탐색을 원 하는데 과연 LinkedList로 이진 탐색이 될까? 참조 포인터로만 이루어져 있는 LinkedList로는 어렵다
왜냐하면 배열의 총 길이를 알아야하고 index Number를 알아야 이진 탐색이 가능하지만 LinkedList에 index Number라는 개념은 없고 오직 참조포인터로만 이루어져 있기 때문이다 !
참고한 레퍼런스
