레코드를 추가 등록하는 경우 B+Tree의 경우 리프 블록의 이곳저곳이 무작위에 가까운 형태로 업데이트되어 가는데 랜덤 액세스는 느리기 때문에 이 비용을 얼마나 감소시키느냐가 성능에 있어 중요하다.

전통적으로 업데이트된 부분을 순서대로 디스크에 써 나갈 것인데 이런 식이라면 속도가 느린 랜덤 라이트가 많이 발생된다.

MySQL(InnoDB)

업데이트된 정보를 메모리나 전용 파일 등에 일시적으로 기록하여 두고 나중에 모아서 단번에 리프 블록을 갱신하는 구조를 채택

랜덤 라이트보다 훨씬 빠른 시퀀셜 라이트(Sequential Write)로 빠르게 처리한다.

MySQL로 간단한 랜덤 INSERT 벤치 마크 실시 결과, HDD가 병목현상을 일으키고 있는 상태에서 이러한 구현으로 인해 초당 2,000회 정도의 INSERT가 가능했다.

병렬 갱신 성능 높이기

리프 분할 : B+Tree 인덱스에 값의 추가/갱신/삭제를 할 경우, 인덱스의 리프 블록의 내용을 이동시킬 필요가 있다.

여러 클라이언트에서 일제히 업데이트가 발행하여 리프 분할이 여기저기에서 일어난 경우, 그것들의 일관성을 갖는 거이 상당히 어려운 작업인데 InnoDB등에서는 인덱스 재편성 처리가 완료될때까지 일체의 참조/갱신 처리를 차단하는 동작을 시행한다.

병령 갱신 성능의 중요도가 높아지면서 B+Tree 인덱스에는 락 프리(Lock Free)로 갱신 가능하게 하는 알고리즘도 제안되고 있어 차세대 데이터베이스에서는 이러한 알고리즘을 사용되게 될 것이다.

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

B+Tree 인덱스는 나무 구주로 된 인덱스로 최 정상이 Root 블록, 최 하위가 Leaf 블록, 그리고 그 사이가 Branch 블록이 들어 간다.

Root 와 Branch는 검색의 키인 사용자 ID에 대해 해당 블록이 어디에 있는지에 대한 정보를 가지고 있고 최하위층의 Leaf 블록은 실제 데이터 영역의 저장 위치의 정보를 가지고 있다.

사용자 65,535는 어디에?

또한 레코드 수가 적으면 루트가 브랜치를 켬하며, 루트와 리프밖에 없는 패턴도 존재 한다. 반대로 많은 경우 4계층 이상의 구성이 될 수도 있다.

다분기 트리와 이진 트리

브랜치 및 리프의 분기 개수가 두 개밖에 없는 것을 이진 트리라고 하고 B+Tree는 다분기 트리라고 부르며, 분기 개수가 두 개 정도가 아닌 수십 개에서 수백 개에 걸치는 경우도 있다. 분기 개수를 많이 하는 이유는 계층의 단수를 줄여서 액세스 횟수를 적게 하기 위해서다.

B-Tree는 B+Tree와는 다르게 브랜치에서도 리프뿐만 아니라 브랜치에서도 키 정보를 가지고 있다.계층구조를 작게 할 수 있다는 장점이 있지만 B+Tree 인덱스는 리프 블록에서 인접한 리프 블록으로 건나가는 것만으로 값의 탐색이 가능하기 때문에 효율적이어서 사실상 RDBMS의 표준으로 널리 사용되고 있다.

사용자 정보를 텍스트 파일로 관리하거나 정보 확인을 위해서 처음부터 탐색하여 찾을 때가지 검색하는 방법은 매우 비 효율 적이다.

이를 개선하기 위해 사용자 정보를 고정 길이로 관리하는 기술은 사용자 정보의 시작 위치는 빨리 찾을 수는 있어도 가변 길이 방식으로 데이터를 관리하는 경우에는 부적합 하다.

해결책은 인덱스 구조를 도입하는 것인데 책의 색인과 같이 키워드와 페이지의 구조로 되어 있고 책의 본문과는 독립적인 형태로 관리되고 있다.

이것을 으용하면 사용자 정보를 취급하는 가변 길이 포맷의 문서와는 별도로 "각각의 사용자 ID마다 파일 상의 시작 위치를 기록한 파일"을 만들어 둠으로써 고속으로 사용자 정보를 찾을 수 있다. 이것이 바로 인덱스 라는 구조 이다.

"키 값, 바이트 위치" 라는 인덱스 항목을 활용할 수 있는데 액세스가 2단계 필요하다는 단점이 있지만, 어느 쪽도 데이터 양에 의존하지 않는 비용으로 값을 취할 수 있기 때문에 데이터의 양에는 의존하지 않고 상당히 빠른 검색이 가능하다

해시 인덱스

앞서 인덳 항목은 키와 바이트 위치의 고정 길이 포맷에 대응을 했는데 키 값의 데이터 항목이 숫자, 문자열, 날씨/시간 등 여러가지를 생각할 수 있으므로 좀 더 범용성을 추구하려면 키 값을 해시 함수를 대입하여 해시 값과 값을 쌍으로 갖는 구조가 즐겨 사용되고 있다.

해시 인덱스는 편리하지만 목적을 당성하지 못하는 일도 종종 있다. 예를들어, "가격이 만원 이하의 선물을 찾고 싶다" 와 같이 키가 되는 것은 가격인데 키의 값이 몇 개로 반환될지 사전에 알 수 없다. 해시 인덱스는 지정한 키 값과 같은 것밖에 찾을 수 없기 때문에 이러한 목적으로는 사용할 수 없다.

결국 많은 검색 작업에서 단지 일부 용도에서만 빠르게 처리할 수 있다 라는 정도로 생각해야 한다.

이를 해결 하기 위해서 나온 것이 바로 B+Tree 라고 불리는 인덱스 구조다.

인덱스만을 읽는 검색 (Index Only Read, Covering index)

데이터베이스 구현에 따라서는 데이터 영역을 읽지 않고 인덱스 영역을 읽는 것만으로 처리를 고속으로 완료할 수 있다. 

예를들어, '가격이 만원 이하인 상품의 개수를 알고 싶다'