기본적으로 명칭에 따라 트리 구조임에는 분명하지만, Binary 와 같은 이진트리는 아니다. 아래 그림을 참조하면, 자식 노드가 반드시 2개 인건 아니고 가변적이다. 그 사실을 제외한다면 기본적으로 트리 알고리즘과 큰 차이점이 있다고 생각 하진 않는다.
루트 노드 — 브랜치 노드- 리프 노드를 가진형태이다.
가장 하위에 있는 노드를 리프노드라고 하고, 최상위에 있는 노드를 루트 노드라고 한다. 루트와 리프 사이에 노드를 브랜치 노드라고 한다. 인덱싱 할 데이터의 수에 따라 브랜치 노드는 없을 수 도 있다.
실제 데이터를 가지고 간단한 구성도를 그려보았다.
데이터베이스에서는 인덱스와 실제 데이터가 별도 저장되며, 따로 관리된다. 그래서 인덱스의 리프노드는 항상 실제 데이터 레코드를 찾아가기 위한 주소 값을 가지고 있다. 그림에서 인덱스는 인덱스 레코드의 값의 순서대로 정렬되어 있다는 점을 확인 하자. 인덱스 레코드는 특정 table 에서 인덱싱을 하겠다고 설정한 컬럼의 값이다. 지금은 country 라는 하나의 컬럼만 인덱스 설정이 된 예시 라고 볼 수 있다. 참고로, 데이터 파일(table) 에서는 실제로 순차적으로 저장되진 않는다. 위 그림 상으로는 순차적이지만, 레코드를 삭제되어 변경한다면, 빈 공간이 생기며 그 빈공간에 다른 데이터가 들어오게 된다. 따라서 순차적이라고 할 수 없다. (mysql 의 innoDB table에서는 pk 순서대로 정렬되어 저장된다.)
문제) 앞쪽 %(후방일치) 가 인덱스를 못타는 이유는?
지금 보고 있는 B-Tree 의 특성 때문이다. 인덱스 레코드에서 저장된 값들을 기준으로 순차정렬된 노드들로 이루어져 있다. 여기서 값의 좌측 부터 비교하여 정렬이 이루어지고, 다음 노드로 보낼 수 있는데 위 조건으로는 어떤 값을 선택해야 할지 알 수 없으니 전체 노드를 다 검색할 수 밖에 없다.
2. 인덱스의 처리
테이블의 레코드를 저장하너가 변경 시 인덱스에도 변경이 일어난다. (물론 인덱스가 있는 테이블의 경우)
2–1 .키 추가
새로운 키 값이 B-Tree 에 저장한다는 것은 바로 끝에다 추가하는 방식이 아니다. 적절한 위치를 검색한 후 저장될 위치를 결정하고, 저장하게 된다. (인덱스의 정렬을 유지하기 위해서다) 인덱스의 키 추가에 대한 비용은 세부사항에 따라서 틀리겠지만, 대략적으로 테이블에 레코드 한 건을 추가하는 비용이 1이라면 , 인덱스 키 추가 비용은 1~1.5 정도로 예측한다. 한 개의 인덱스가 있는 테이블의 경우 레코드 추가 시 2~2.5 의 비용이 든다는 의미이다. 결국 이 비용은 대부분 디스크 작업에서 발생한다.
중요한 것은 인덱스 추가 비용은 존재하며, INSERT , UPDATE 와의 작업비용에 영향을 미친다는 것이다. 그래서 인덱스의 설계는 필요한 부분만 하는 것이 좋다고 말하는 것이다.
InnoDB 의 경우 인덱스의 추가가 즉시 이루어지거나, 지연 처리 될 수 있다.
InnoDB 의 버퍼 풀에 의하여 처리 시점이 결정된다. 버퍼 풀은 InnoDB 엔진에서 핵심적인 부분이라고 한다. 버퍼 풀은 간단하게 정의하면, 디스크의 데이터파일이나 인덱스 정보를 메모리에 캐시해 두는 공간이다. 쓰기 작업을 지연시켜 일괄 작업으로 처리할 수 있게 해주는 버퍼 역할도 같이 한다. 그리고 메모리가 디스크보다 처리 속도가 훨씬 빠른다는 사실을 숙지하고 다음 순서에 대하여 이해하면 도움이 될 것이다.
(1) 사용자의 INSERT 쿼리 실행-> (2) 버퍼 풀에 추가 될 B-Tree 리프노드 (페이지)가 존재한다면 즉시 키 추가 작업 (캐쉬이기 때문에 없을 수도 있다)-> (3) 즉시 추가 하지 않았다면 인서트 버퍼에 추가할 키값과 레코드의 주소를 기록하고 사용자의 쿼리 실행 완료 -> (4) 백그라운드 작업으로 인덱스 페이지를 읽을 때마다 인서트 버퍼에 병합해야할 인덱스 키값이 있는지 확인 후 병합 (B-Tree 에 추가됨)
* 서버 자원의 여유가 있으면 MySQL 서버의 인서트 버퍼 머지 스레드가 인서트 버퍼에 임시 저장된 정보를 병합하기도 한다.
