인덱스 B-TREE

 책의 "찾아보기"를 인덱스에 비유하면 책의 내용은 데이터 파일에 저장된 레코드의 주소에 비유됩니다. 데이터 베이스는 모든 데이터를 풀스캔 하기 때문에 오래 걸리지만 칼럼의 값과 해당 레코드가 저장된 주로를 키와 값의 쌍으로 삼아 인덱스를 만들어 두어 정렬을 하기때문에 빠르게 데이터를 가져올 수 있습니다.

 

B-TREE 인덱스

ㅇ데이터베이스의 인덱싱 알고리즘 가운데 가장 일반적으로 사용되고, 범용적이고 가장 먼저 도입된 알고리즘 입니다.일반적으로 B+-또는 B*-TREE가 사용됩니다.그리고 Binary 가 아닌 Balanced의 B를 의미 합니다.

칼럼값으 원래 값을 변형시키지 않고 인덱스 구초제 내에서 항상 정렬된 상태로 유지합니다.

 

최상위에 하나의 ROOT가 존재하고 그 하위에 자식 노드가 붙어 있는 형태입니다. 트리구조의 가장 하위에 있는 노드를 Leaf node라 하고, 중간 노드를 Branch node라 합니다. 인덱스와 실제 데이터가 저장된 데이터는 따로 관리되는데, 인덱스의 Leaf node는 항상 실제 데이터의 레코드를 찾아가기 위한 주솟값을 가지고 있습니다. 

 

그림에서 보면 인덱스의 키 값은 모두 정렬돼 있지만, 데이터 파일의 레코드는 정렬돼 있지 않고 임의의 순서로 저장돼 있습니다. 

*대부분 rdms의 데이터 파일에서 레코드는 특정 기준으로 정렬되지 않고 임이의 순서로 저장됩니다. 하지만 InnoDB 테이블에서 레코드는 클러스터되어 디스크에 저장되므로 기본적으로 프라이머리 키 순서로 정렬되어 저장됩니다.

위 를 보면 MyISAM 레코드 주소는 테이블의 생성 옵션에 따라 레코드가 테이블에 INSERT된 순번이거나 데이터 파일 내의 위치(Offset)입니다.  OFFSET을 RowID로 사용하며 RowID로 데이터 파일을 바로 찾을 수 있다.

 

InnoDB에서는 프라이머리키가 RowID 역활을 하며 두 인진 의 인덱스에서 가장 큰 차이점은 Secondary Index를 통해 데이터 파일의 레코드를 찾아가는 방법에 있습니다.  MyISAM 테이블은 세컨더리 인덱스가 물리적인 주소를 가지고, InnoDB 테이블은 PK를 주소처럼 사용하기 때문에 논리적인 주소를 갖는다고 할 수 있습니다. 인덱스를 통해 리프 노드에서 PK를 찾고, PK를 이용해 PK index를 한번더 검색해야 PK index의 리프 페이지에 저장된 레코드를 읽을 수 있습니다.

 

 그리고 InnoDB은 클러스터링 인덱스로 저장됩니다. 여기서 클러스터링 인덱스란 테이블의 레코드가 PK 값으로 정렬된 경우를 의미하며 클러스터링 테이블이라고도 합니다. 즉, 테이블의 레코드 순서는 PK 값에 크게 의존한다는 것이고, 만약 PK를 변경했다면 테이블 내에서 위치가 변경될 수 있습니다. 이는 레코드의 주소가 변경되었다는 의미입니다. 만약 RowId에 레코드의 물리적 주소를 가지고 있었다면 PK 값이 변경될 때마다 인덱스에 저장된 주소값도 변경해야합니다. 이러한 오버헤드를 줄이기 위해 InnoDB 테이블을 모든 Secondary Index는 레코드가 저장된 주소가 아니라 PK 값을 저장하도록 구현되어있습니다.

 

인덱스 키 추가

 새로은 키 값이 저장될 때 테이블의 스토리지 엔진에 따라 새로운 키 값이 즉시 인덱스에 저장될 수도 있고 그렇지 않을 수도 있습니다. 적절한 위치를 결정하고 레코드의 키 값과 대상 레코드의 주소 정보를 B-TREE Leaf node에 저장합니다.

 

삭제

  해당 키값이 저장된 B-Tree의 리프 노드를 찾아서 그냥 삭제 마크만 하면 작업이 완효됩니다. 이렇게 삭제 마킹된 인덱스 키 공강은 계속 그대로 방치하거나 재활용할 수 있습니다. MySQL5.5 이상 버전의 InnoDB 스토리지 엔진에서는 이 작업 또 한 버퍼링 되어 지연 처리 될 수 있으며, MySQL 서버가 내부적으로 처리합니다. MyISAM이나 MEMORY 스토리지 엔진의 테이블에서는 체인지 버퍼와 같은 기능이 없으므로 인덱스 키 삭제가 완료된 후 쿼리 실행이 완료됩니다.

 

변경

단순히 인덱스상의 키 값만 변경하는 것을 불가능 하므로 먼저 키 값을 삭제 한 후 다시 새로운 키 값을 추가하는 형태로 처리됩니다. 그러므로 InnoDB 스토리지 엔진을 사용하는 테이블에 대해서는 이 작업 모두 체인지 버퍼를 활용해 지연 처리 될 수 있습니다.

 

검색

위의 작업에 추가비용을 감당하는 이유는 빠른 검색을 위해서입니다. 트리 탐색을 하는 데 검색을 할 때만 사용하는 것이 아니라 UPDATE 또는 DELETE를 처리하기 위해 항상 해당 레코드를 먼저 검색해야 할 경우에도 사용됩니다.