인덱싱 (10분 테코톡)

Bonjugi·2023년 2월 11일

이진트리의 단점

아래와 같이 한쪽으로 노드가 늘어날수 있다.
높이(뎁스) 가 다르다. (한쪽으로 편향적이다)
이러면 26을 찾을때는 2뎁스, 18을 찾을때는 4뎁스가 된다.

그래서 나온것이 B-tree 인덱스.
높이가 같다. (밸런스)
B-tree 인덱스는 clustered index, non-clustered index 로 나뉜다.

clustered index

영상 위치 링크 : https://youtu.be/P5SZaTQnVCA?t=568

루트페이지, 브랜치페이지, 리프페이지가 로 존재한다.
이런 구조는 이는 non-clustered index도 마찬가지 이다.
다만, clustered index는 리프에 데이터가 있다.
즉 데이터도 정렬 되어 있다는 특징이 있다.

인덱스에 삽입 발생시 일어나는 일

아래 그림이 있고, 여기에 KKK 를 추가로 삽입 한다고 가정해 보자.
여겨볼것은, LLL 밑에 들어가야 하는데 자리가 없다.
과연 어떻게 동작할까?

KKK를 추가하기 위해 새로운 페이지를 만들고 쓰면 될거같다.
그런데 생각보다 많은 일이 발생한다.
아래 그림을 보자.

새로운 페이지를 만들고 LLL을 이동 시킨다.
KKK만 새로운 페이지에 두면 밸런스드하지 않기 때문 이다.
이를 페이지 분할 이라고 한다.
그리고 새로 생긴 페이지를 트리구조로 만들기 위해 상위 루트 페이지를 만들어야 한다.
그래서 2번의 루트페이지를 생성하는 과정도 있다.

이런 과정은 대용량의 데이터라면 상당히 힘든 작업이 될수 있다.
clustreed-index 를 균형있게 재정렬 해야 되는데, 이는 곧데이터 를 재정렬 한다고 생각해도 되며, 페이지를 다시만들고 트리를 다시 구성해야 함을 의미한다.
이는 delete가 발생할때도 유사한 과정이 진행된다.

clustered index 요약

clustered index 는 끝에 데이터가 달려있다.
데이터가 정렬되어있다고 봐도 무방하다.
cud 발생시 밸런스를 유지하기 위해 페이지 분할 및 재정렬이 발생한다. 이는 부하가 꽤 큰편이다.
delete 도 마찬가지의 부하를 받는다.

non-clustered index

영상 위치 링크 : https://youtu.be/P5SZaTQnVCA?t=797

리프페이지에 데이터를 직접 가지고 있지 않음. (대신 페이지 주소를 가지고있다)
데이터페이지에 데이터가 정렬되어있지 않아도 된다.
대신에 인덱스는 정렬되어 있다.
그래서 사이 사이에 값이 들어올때는 clustered index 와 마찬가지로 페이지 분할이라던지 노드 재정렬이 발생한다.
그래도 비교적 clustered index 보다는 오버헤드가 적다.
하지만 조회는 리프페이지에 주소를 갖고있으므로 한번 더 가져와야해서

non-clustred index 요약

non-clustered의 리프에는 clustered와 달리 데이터가 있진 않다. 데이터페이지의 주소를 가지고 있다.
non-clustered도 clustered와 마찬가지로 insert, delete 할 시 페이지 분할 및 재정렬이 일어난다. clustered에 비해 상대적으로 유리하다.
cud 에는 상대적으로 유리하지만 r은 불리하다. (뎁스가 1번더 있음)