B-Tree 인덱스

B-Tree란?

 

- B-Tree는 데이터베이스의 인덱싱 알고리즘 가운데 가장 일반적으로 사용되고, 또한 가장 먼저 도입된 알고리즘

 

- 가장 범용적인 목적으로 사용되는 인덱스 알고리즘

 

- B-Tree의 B는 "Binary(이진)"의 약자가 아니라 "Balanced"를 의미

 

- B-Tree는 컬럼의 원래 값을 변형시키지 않고 인덱스 구조체 내에서는 항상 정렬된 상태로 유지

 

구조 및 특성

 

- 트리 구조의 최상위에 하나의 루프 노드가 존재하고 하위에 자식 노드가 붙어 있는 형태

 

- 트리 구조의 가장 하위에 있는 노드를 리프노드라고 부름

 

- 루트 노드도 리프 노드도 아닌 중간에 있는 노드를 브랜치 노드라고함

 

- DB에서 인덱스와 실제 저장된 데이터는 따로 관리되는데, 인덱스의 리프 노드는 항상 실제 데이터 레코드를

 

  찾아가기 위한 주소 값을 가지고 있음

 

B-Tree 구조

 

 - 인덱스의 키 값은 모두 정렬되어 있지만 데이터 파일의 레코드는 정렬되어 있지 않고 임의의 순서대로 저장되어 있음

 

    많은 사람들이 파일의 레코드는 INSERT된 순서대로 저장되는 것으로 생각하지만 그렇지 않다.

 

     만약, 테이블의 레코드를 삭제나 변경이 전혀 없이 INSERT만 수행한다면 맞을 수도 있지만 레코드가 삭제되어

 

     빈 공간이 생기면 그 다음의 INSERT는 삭제된 공간을 가능한 재활용하도록 DBMS가 설계되기 때문에 항상

 

     INSERT 된 순서대로 저장되는 것은 아니다.

 

   -> BUT InnoDB 테이블에서 레코드는 클러스터되어 디스크에 저장되므로 기본적으로 프라이머리 키 순서대로 

 

      정렬되어 저장 됌 ( ORACLE이나 MY-SQL)

 

        * 클러스터링 : 비슷한 값들은 최대한 모아서 저장하는 방식

 

   - 인덱스는 테이블의 키 컬럼만 가지고 있으므로 나머지 컬럼을 읽으려면 데이터 파일에서 해당 레코드를 찾아야함

 

     이를 위해 인덱스의 리프 노드는 데이터 파일에 저장된 레코드의 주소를 가지게 된다.

 

 

인덱스 키 추가

 

 - 새로운 키값이 B-Tree에 저장될 때 테이블의 스토리지 엔진에 따라 새로운 키 값이 즉시 인덱스에 저장될 수도 있고

 

   그렇지 않을 수도 있다.

 

   B-Tree에 저장될 때는 저장될 키값을 이용해 B-Tree상의 적절한 위치를 검색해야 한다.

 

   저장될 위치가 결정되면 레코드의 키값과 대상 레코드의 주소 정보를 B-Tree의 리프 노드에 저장합니다.

 

   만약 리프 노드가 꽉 차서 더는 저장할 수 없을 때는 리프 노드가 분리되야 하는데,

 

   이는 상위 브랜치 노드까지 처리의 범위가 넓어진다.  

 

   이러한 작업 탓에 B-Tree는 상대적으로 쓰기 작업(새로운 키를 추가하는 작업)에 비용이 많이 드는 것으로 알려짐

 

인덱스가 보안에 사용되는 이유

 

 - InnoDB 테이블에서 지원하는 레코드의 잠금이나 넥스트 키 락(갭 락)이 검색을 수행한 인덱스를 잠근 후 테이블의

     

  레코드를 잠그는 방식으로 구현