텍스트로 데이터를 관리한다고 해보자.
사용자 정보를 선형으로 탐색하면 너무 오래걸린다.
그래서 사용자ID에 100을 곱한 값의 바이트에 사용자 정보를 저장하기로 했다.
사용자 ID를 받으면 순식간에 이동이 가능하다.

하지만 사용자 정보가 언제나 100바이트안에 다 들어가지 않을 수도 있다. 이름이 너무 길거나, ID가 너무 길거나 등 고정 길이 방식으로 관리하는 건 실용적이지 않다는 것이다.

💡 인덱스

각각의 사용자ID마다 파일 상의 시작 위치를 기록한 파일을 인덱스라고 한다.

위의 고정길이 방식을 인덱스에 적용해보자

사용자ID가 1234이고 인덱스의 키와 위치는 각각 4바이트로 하나의 쌍이 8바이트를 차지한다하자.
그럼 1234ID의 정보에 대한 위치는 1234x8 바이트를 읽으면 바로 알 수 있다.

엑세스를 2번 거쳐야 하지만 인덱스와 데이터저장 파일 모두 데이터 양을 고려할 필요없이 상당히 빠른 검색을 할 수 있게된다.

데이터를 업데이트하면 인덱스도 함께 업데이트 되야하므로 데이터 업데이트 비용이 증가한다. 대신 검색을 극적으로 고속화할 수 있다.

💡 해시 인덱스

위에서 키 값을 사용자 ID 4바이트로 고정시켰다.
하지만 키 값이 숫자가 될 수도, 날짜가 될 수도 있을 거라는 생각을 한다면 고정 길이로 맞추기가 어렵다.

실제 데이터베이스에서는 키 값을 해시함수에 대입해서 사용한다.
이런 인덱스를 해시인덱스라고 한다.

해시 계산의 시간복잡도는 O(1)밖에 안된다.

✅ 해시의 충돌

다른 키 값인데 해시함수에 넣으면 같은 해시 값을 가지게 되는 경우가 있다. 따라서 이 충돌을 감지하는 구조가 필수적이다.
그렇기에 원래 해시계산의 시간복잡도는 O(1)이지만 충돌 판정 및 재계산까지 고려한다면 데이터 양이 증가할 수록 처리 시간이 함께 증가하게 된다.
그럼에도 고속이라는 것은 변함없다.

✅ 해시인덱스의 문제점

• 조건이 키가 될 수 없음
  • 키가 '가격'이며 조건은 '1000원 이하' 인 것.
• 일부가 일치하는 키값
  • 'A'로 시작하는 사람찾기
• 정렬
  • 가격이 저렴한 순서로 반환

💡 B+Tree 인덱스

B+Tree 인덱스는 나무 구조로 된 인덱스를 말한다.
최고층을 루트 블록, 최하층을 리프 블록, 사이의 것들을 브랜치 블록이라고 한다.

루트 블록과 브랜치 블록은 키에 대한 블록의 위치에 관한 정보를 가지고있다. 그렇게 따라가다 만나는 리프블록에는 최종적으로 찾는 정보가 존재한다.
그래서 해시 인덱스에 비해서 많은 엑세스가 필요하다.

이진트리에 대해 알고 있을 것이다. B+Tree는 다분기트리이다.
다분기로 하는 이유는 계층의 단수를 줄여서 엑세스 횟수를 적게 하기 위해서이다.

💡 B-가 아닌 B+인 이유

B-Tree는 브랜치에서도 값을 가질 수 있는 구조이다.
따라서 주변의 리프가 아닌 브랜치로 가서 값이 존재하는지 확인해야한다.

그에 반해 B+Tree는 리프 브록에서 인접한 리프블록으로 건너가는 것만으로 값의 존재를 확인할 수 있으므로 훨씬 효율적이다. 그래서 B+Tree가 RDBMS에서 표준적으로 사용되고 있다.

또한 B+Tree는 해시인덱스에서는 불가능했던 부등호나, 범위검색을 리프 블록을 스캔하는 것으로 가능하기 때문에 유연성이 높다.

💡 인덱스의 성질

• 고유성 보장
  해시 인덱스의 경우 키 값이 같다면 해시값역시 같게디고, B+Tree인덱스의 경우 동일 리프에 도달할 것이기 때문에 쉽게 중복 체크를 할 수 있다.

• 인덱스 병합
  OR조건 검색은 한번의 검색에서 두 개 이상의 인덱스를 동시에 사용하여 각각의 결과에서 원하는 레코드를 꺼내야 한다. 인덱스병합은 각 인덱스에서 각각 검색을 실시해 대상의 행 번호를 추출하고, 그 다음 각각의 결과에 대해 집합 연산을 수행해서 마지막으로 남은 행 번호에 대한 데이터를 읽어간다.

💡 업데이트 비용

앞에서 말했지만 인덱스는 업데이트 비용이 추가된다. B+Tree인덱스에 값을 추가,갱신,삭제를 하면 리프 블록의 내용을 이동시키는데 이를 리프분할이라 한다.

여러개의 클라이언트가 동시에 업데이트를 한꺼번에 요청하면 리프 분할이 여기저기 일어나면 일관성을 가지기 어려워진다. 그래서 MySql에서는 인덱스의 재편성 처리가 완료될 때까지 다른 처리를 차단하는 동작을 시행한다.
또한 사용자에게는 테이블이 한 개로 보이지만 내부적으로 복수로 분할 관리하는 파티션 테이블을 사용해서 병렬 갱신을 가능케 하기도 한다.