Portfolio

해시 인덱스 B+ Tree(다분기 트리 ≠ 이진 트리) 인덱스 RDBMS에서는 어떻게 최적화를 실현하고 있는가?

💡

데이터 건수의 증가에 비례하여 검색 시간이 늘어나면 많은 양의 데이터를 처리하여야 하는 환경에서는 제대로 작동할 수 없다. 그래서 인덱스를 사용함으로써 검색을 실제 가능한 시간 안에 끝낼 수 있게 되는 것 인덱스를 이용하는 것이 항상 좋은 것은 아닌 것이, 데이터를 불필요하게 갖기 때문에 데이터 크기가 증가하고 색인을 업데이트하기 위해 불필요한 처리가 필요 업데이트 속도의 저하는 특히 데이터의 양이 서서히 증가해 가는 타입의 애플리케이션에서 심각해지기 쉽기 때문에 인덱스를 함부로 부여하는 것이 아니라 필요한 것에 대해 균형 있게 부여하는 것이 중요.

해시 인덱스

키 값을 해시 함수에 대입하여 해시 값과 값의 쌍을 갖는구조로 사용함

DB 제품에서는 해시 충돌 또한도 고려하여 설계가 되어 있음

단점(해시 인덱스가 부족한 부분들)

가격이 10,000원 이하의 선물을 찾고 싶다
제목이 “Final”로 시작하는 게임 리스트를 찾고 싶다 — 범위 검색(Range Search)
일기 포스팅 시간이 최신 순으로 정렬하고 싶다 — 정렬(Sort)

B+ Tree(다분기 트리 ≠ 이진 트리) 인덱스

루트 블록과 브랜치 블록은 검색의 키인 사용자 ID에 대해 해당 블록이 어디에 있는지에 대한 정보를 가지고 있음

최하층의 리프 블록은 실제 (데이터 영역에서의) 저장 위치의 정보를 가지고 있음 → 광범위하게 걸친 검색에서 자기 자신의 리프 블록 뿐 아니라 주변의 리프 블록으로 넘어가 액세스 해 나감으로써 더 효율적으로 값 탐색이 가능함

B-Tree는 모든 값을 리프 블록에서만 갖도록 제한하지 않고 브랜치에서도 값을 가질 수가 있음 → B-Tree는 값을 찾기 위해 브랜치로 올라가야 하는 상황이 발생하지만, B+Tree는 인접한 리프 블록을 건너가는 것으로 값의 탐색이 가능하므로 조금 더 효율적임.

위의 예시에서 ID 65,535를 찾기위해 루트 블록 → 브랜치2 → 리프 170 → 실제 데이터(3,276,750 번째 바이트)

레코드의 수가 적으면 루트가 브랜치를 겸하며, 루트와 리프밖에 없는 패턴도 존재함

레코드 수가 매우 많은 경우 브랜치 아래에 브랜치가 들어가는 4계층 이상의 구성이 될 수도 있다

B+Tree 인덱스를 사용하면 등호 검색은 물론 부등호나 전방 일치 검색 등의 범위 검색도 리프 블록을 스캔하는 것만으로 완결할 수 있음

RDBMS에서는 어떻게 최적화를 실현하고 있는가?

인덱스를 고유성을 보증하는 목적으로도 사용할 수 있음

해시 인덱스라면 동일한 id인 경우 반드시 동일한 해시값
B+Tree 인덱스면 동일 리프 블록에 도달, 적은 코스트로 쉽게 중복 체크를 할 수 있음

멀티 컬럼 인덱스 : [사용자 ID가 100이고 마지막 수정 날짜가 2009년 9월 30일 이전의 것] 이라는 조건으로 검색하고 싶을 때, 사용자 ID와 최종 업데이트 여러 조건의 인덱스로 검색하는 방법

인덱스만을 읽는 검색 : 검색 패턴에 따라 인덱스를 읽는 것만으로 처리가 완결되는 경우가 있음

예로 가격이 10,000원 이하인 상품의 개수를 알고 싶다 → 가격 인덱스가 있으면 해당 인덱스를 보는 것만으로 결과 구할 수 있음. 데이터 영역에 액세스 필요 x

인덱스 병합 : 한 번의 검색에서 두 개 이상의 인덱스를 동시에 사용하여 각각의 결과에서 원하는 레코드를 꺼내려고 하는 발상. 각 인덱스에서 각각 검색 실시 후 결과에 대해 AND, OR 조건 적용

💡

랜덤 액세스는 느리다 데이터베이스의 성능 특성을 이해하는 데 있어 매우 중요한 것이 랜덤 액세스 성능을 이해하는 것이다. 데이터베이스에서는 무정지성을 확보하기 위해서 갱신한 데이터를 디스크에 써야 한다. 또한 메모리에 맞지 않는 규모의 데이터를 취급하는 것이 대부분이며, 메모리에 올라와 있지 않은 데이터를 읽기 위하여 디스크로부터의 로드가 발생 대부분의 경우 이것들은 랜덤 액세스다. 랜덤 액세스 시간은 HDD의 경우라면 대개 디스크가 반 정도 회전하는 시간. 그러나 SSD의 경우는 랜덤 액세스가 빠를 듯. 그러나 그 한계 이상으로 랜던 액세스 요청이 들어와 버리면 처리를 수행할 수 없게 되는 것은 마찬가지

업데이트(CUD) 비용 절감을 위한 노력

디스크에 모아서 기록하기

레코드를 추가 등록하는 경우 B+Tree 인덱스에도 값을 등록해야 함

사용자 데이터베이스에 대한 사용자 ID는 사용자 ID에 대해 오름차순으로 등록될 가능성이 높지만, 상품 데이터베이스의 상품 가격은 오름차순으로 등록된다는 보장이 전혀 없음 ⇒ 인덱스의 리프 블록의 이곳저곳이 무작위에 가까운 형태로 업데이트 됨. 랜덤 액세스는 느리기 때문에 이 비용을 얼마나 감소 시키느냐가 성능에 있어 중요함

데이터베이스에서는 무정지성을 높이기 위해 업데이트된 부분(블록)을 최대한 빨리 디스크에 저장해야 함

전통적인 방식으로 구현 하면 업데이트된 순서대로 디스크에 써 나갈 것이고 이렇게 되면 속도가 느린 random write가 많이 발생하게 됨

이에, 업데이트된 정보를 메모리나 전용 파일 등에 일시적으로 기록해 두고 나중에 모아서 단번에 리프 블록을 갱신하는 구조를 채택하고 있는 DB가 MySQL임. Random write x. Sequential Write로 단번에 처리

병렬 갱신 성능 높이기

B+Tree 인덱스에 값의 추가/갱신/삭제를 할 경우, 인덱스의 리프 블록의 내용을 이동시킬 필요가 있게 됨. 이러한 처리를 리프 분할 이라고 함

여러 클라이언트에서 일제히 업데이트가 발생하여 리프 분할이 여기저기에서 일어나는 경우, 그것들의 일관성을 갖는 것은 상당히 어려운 작업임

이 상황은 실제로 존재하기에 MySQL(InnoDB) 등에서는 인덱스의 재편성 처리가 완료될 때까지 일체의 참조/갱신 처리를 차단하는 동작을 시행함

재편성 조작 자체는 금방 끝나지만 동시에 대량의 클라이언트로부터 동일 테이블에 대해 일제히 INSERT/UPDATE/DELETE를 시행하여도 동시성이 그다지 높아지지 않는 문제가 있음

B+Tree 인덱스에는 Lock Free 로 갱신 가능하게 하는 알고리즘도 제안되고 있어 차세대 데이터베이스에서는 이러한 알고리즘이 사용되게 될 것임

현재 MySQL에서 이것을 해결하는 가장 빠른 방법은 파티션 테이블을 사용하는 것. 파티션 테이블이란 사용자에게 테이블이 한 개로 보이지만 내부적으로는 복수로 분할 관리되는 것임. 인덱스도 복수로 구분하고 있기 때문에 병렬 갱신이 가능함