DBMS에서 주로 사용되는 알고리즘은 B+-Tree 또는 B*-Tree가 사용된다.
B-Tree는 컬럼의 원래 값을 변형시키지 않고 인덱스 구조체 내에서는 항상 정렬된 상태를 유지한다. 전문 검색과 같은 특수한 요건이 아닌 경우, 대부분 인덱스는 거의 B-Tree를 사용할 정도로 용도에 적합한 알고리즘이다.
B-Tree는 최상위에 하나의 루트 노드가 존재하고 그 하위에 자식 노드가 붙어 있는 형태다.
트리 구조의 최하위의 있는 노드를 리프 노드라고 한다.
루트 노드와 리프 노드 사이의 있는 노드를 브랜치 노드라고 한다.
인덱스의 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주소 값을 가지고 있다.
인덱스의 키값은 모두 정렬돼어 있지만 데이터 파일의 레코드는 정렬되어 있지 않고 임의의 순서로 저장된다.
오라클은 물리적인 레코드 주소, MySQL의 MyISAM은 내부적인 레코드의 아이디, MySQL의 InnoDB는 프라이머리 키에 의해 클러스터링 되기 떄문에 프라이머리 키값 자체가 주소 역할을 한다.
새로운 키값이 B-Tree에 저장 될때 테이블의 스토리지 엔진에 따라 새로운 키값이 즉시 인덱스에 저장될 수도 있고 그렇지 않을 수도 있다. B-Tree에 저장될 때는 키 값을 이용해 B-Tree 상의 적절한 위치를 검색해야 한다. 저장될 위치가 결정되면 레코드의 키 값과 대상 레코드의 주소 정보를 B-Tree의 리프 노드에 저장한다.
만약 리프 노드가 꽉 차서 더는 저장할 수 없을 때는 리프 노드가 분리돼야 하는데, 이는 상위 브랜치 노드 까지 처리의 범위가 넓어진다. 이러한 작업 탓의 B-Tree는 상대적으로 쓰기 작업에 비용이 많이 든다.
MyISAM이나 Memory 스토리지 엔진을 사용하는 테이블은 INSERT 문장이 실행되면 즉시 새로운 키 값을 B-Tree 인덱스의 반영한다. 즉 B-Tree에 키를 추가하는 작업이 완료될 때 까지 클라이언트는 쿼리의 결과를 받지 못하고 기다리게 된다.
InnoDB 엔진은 상황에 따라 적절하게 인덱스 키 추가 작업을 지연시켜 나중에 처리할지, 아니면 바로 처리하지 결정한다.
쿼리 실행
InnoDB의 버퍼 풀에 새로운 키값을 추가해야할 리프노드가 존재한다면 즉시 키 작업 처리
버퍼풀에 B-Tree의 리프 노드가 없다면 인서트 버퍼에 추가할 키 값과 레코드의 주소를 임시로 기록해 두고 작업완료
백그라운드 작업으로 인덱스 페이지를 읽을 때마다 인서트 버퍼에 머지해야할 인덱스 키값이 있는지 확인한 후, 있다면 병합함
데이터 베이스 서버 자원 여유가 생기면 MySQL 서버의 인서트 버퍼 머지 스레드가 조금씩 인서트 버퍼에 임시 저장된 인덱스 키와 주소 값을 머지시킴
해당 키 값이 저장된 B-Tree의 리프 노드를 찾아서 삭제 마크만 하면 작업이 완료된다. 이렇게 삭제 마킹된 인덱스 키 공간은 계속 그대로 방치하거나 또는 재활용할 수 있다. 인덱스 키 삭제로 인한 마킹 작업 또한 디스크 쓰기가 필요하므로 이 작업 역시 디스크 I/O 필요한 작업이다. MySQL 5.5이상의 버전의 InnoDB 스토리지 엔진에서는 이 작업 또한 버퍼링되어 지연 처리가 될 수도 있다.
인덱스의 키값은 그 값에 따라 저장될 리프 노드의 위치가 결정되므로 B-Tree의 키값이 변경되는 경우 단순히 인덱스상의 키값만 변경이 불가능하다. B-Tree의 키값 변경작업은 먼저 키 값을 삭제한 후, 다시 새로운 키 값을 추가하는 형태로 처리된다.
INSERT, UPDATE, DELETE 작업을 할 때 인덱스 관리에 따르는 추가 비용을 감당하면서 인덱스를 구축하는 이유는 관리에 빠른 검색을 위해서다.
인덱스를 검색하는 작업은 B-Tree의 루트 노드부터 시작해 브랜치 노드를 거쳐 최종 리프 노드까지 이동하면서 비교작업을 수행하는데, 이 과정을 트리 탐색이라고 한다.
인덱스 트리 탐색은 UPDATE나 DELETE를 처리하기 위해 항상 해당 레코드를 먼저 검색해야 할 경우에도 인덱스가 있으면 빠른 검색이 가능하다.
B-Tree 인덱스를 이용한 검색은 100% 일치 또는 값의 앞부분만 일치하는 경우에 사용할 수 있다. 부등호 비교나 값의 뒷부분이 일치하는 경우에는 B-Tree 인덱스를 이용한 검색이 불가능하다.
인덱스를 이용한 검색에서 중요한 사실은 인덱스의 키값에 변형이 가해진 후 비교되는 경우에는 절대 B-Tree의 빠른 검색 기능을 사용할 수 없다는 것이다. 따라서 함수나 연산을 수행한 결과로 정렬한다거나 검색하는 작업은 B-Tree의 장점을 이용할 수 없으므로 주의해야 한다.
InnoDB 스토리지 엔진에서 인덱스는 더 특별한 의미가 있다. InnoDB 테이블에서 지원하는 레코드 잠금이나 넥스트 키 락이 검색을 수행한 인덱스를 잠근 후 테이블의 레코드를 잠그는 방식으로 구현되어 있다. 따라서 UPDATE나 DELETE 문장이 실행될 때 테이블에 적절히 사용할 수 있는 인덱스가 없으면 불필요하게 많은 레코드를 잠근다. 심지어 모든 레코드를 잠글 수도 있다.