B-Tree 인덱스

B-Tree 인덱스의 구조, 특성, 데이터 읽기, 가용성에 대해

구조, 특성

인덱스 리프 노드의 각 키 값은 테이블의 데이터 레코드를 찾아가기 위한 물리적인 주소 값을 가지고 있다.
인텍스의 키 값들은 모두 정렬돼 있지만, 테이블의 데이터 레코드는 기본적으 로 정렬돼 있지 않고 INSERT 된 순서대로 저장된다.
MongoDB 컬렉션의 인덱스에서는 항상 인덱스 필드의 값과 주소 값 (MongoDB 내부적으로는 Recordld라고 함)의 조합이 인덱스 레코드로 구성된다.
단일 필드는 인덱스에 이름이 저장되지 않지만, 서브 도큐먼트는 자식 필드의 이름이 모두 저장되므로 이름의 길이가 인덱스의 크기에 영향을 미친다.

인덱스 키

추가

테이블에 레코드를 추가하는 비용이 1이라면, 키를 추가하는 비용은 1~1.5다.
컬렉션에 3개의 인덱스가 있다면 5.5정도의 비용이 든다는 것.
메모리와 CPU에서 처리하는 것이 아니라 디스크로부터 인덱스 페이지를 읽어오는데 걸리는 시간이다.

검색

트리 검색(Tree traversal): B-Tree의 루트 노드 → 브랜치 노드 → 최종 리프 노드까지 비교하며 인덱스를 검색하는 작업
검색은 **FIND 쿼리에서만 하는게 아니라 UPDATE, DELETE 시에도 먼저 해야 하기 때문에, 이 때에도 빠른 검색이 가능하게 한다.
B-Tree 인덱스를 이용한 검색은 100% 일치 또는 앞부분 일치만 사용할 수 있고, 부등호 비교에는 사용할 수 없다.

변경

키 값을 찾아 삭제한 다음에 추가한다.
위 명시된 삭제, 추가 작업을 각각 진행한다고 보면 된다.

삭제

삭제된 인덱스에 마크한 뒤 방치되거나 재활용된다.
내부적으로 캐시를 가지고 있기 때문에 데이터 마크를 위한 작업은 사용자 요청과는 비동기로 처리된다.

인덱스 사용에 영향을 미치는 요소

인덱스 키 값의 사이즈

B-Tree의 자식 노드는 인덱스 페이지의 크기와 키 값의 사이즈에 따라 결정된다.
인덱스의 키 값이 커지면 오버헤드가 생길 수 있다. (한 페이지에 저장할 수 있는 인덱스 키가 줄어들기 때문)
- 페이지 or 블록
  - 디스크 읽기, 쓰기 작업(데이터 저장)의 최소 단위
  - 스토리지 엔진이 데이터를 관리하는 기본 단위
  - 인덱스도 페이지 단위로 관리 (루트, 브랜치, 리프 노드를 구분한 기준도 페이지 단위)
- 예시
  - 인덱스 페이지가 16KB이고 인덱스 키의 크기가 16바이트, 32바이트인 상황이 있다면 전자는 인덱스 키 585개, 후자는 372개를 저장할 수 있다.
  - 도큐먼트 500개를 읽어야 하는 상황에서 전자는 인덱스 페이지를 한 번 읽어 해결하지만, 후자는 2번 이상 디스크에서 인덱스 페이지를 읽어와야 하기 때문에 디스크 I/O로 인해 느려진다.
  - 스토리지 엔진은 메모리 캐시를 사용하기 때문에 위 예시가 항상 맞는 것은 아니지만, 인덱스 키값의 사이즈가 작을 수록 오버헤드가 최소화된다.
    - 캐시: 서버의 캐시에 자주 사용되는 데이터 페이지가 적재되어 매번 읽지는 않을 수 있다.

B-Tree의 깊이

값을 검색할 때 몇 번이나 랜덤하게 디스크를 읽어야 하는지와 직결된다.
인덱스 키 값의 사이즈가 클 수록 인덱스 페이지가 담을 수 있는 인덱스 키의 개수가 작아지고, 그로 인해 같은 레코드 건수라고 하더라도 깊이가 깊어져서 디스크 읽기가 더 많이 필요해진다.
하지만 깊이가 5이상으로 깊어지는 경우는 거의 없어 깊이로 인해 성능 저하가 되는 현상은 거의 없다.

selectivity & cardinality

선택도가 높은 컬럼에 인덱스를 걸면 인덱스 효율이 높아진다. 하지만 선택도가 높지 않아도 인덱스를 만드는 것이 훨씬 나은 경우도 있다.

인덱스에서 선택도(selectivity) 또는 기수성(cardinality)은 거의 같은 의미로 사용된다.
집합의 크기(cardinality)
- 값이 유니크할 수록 집합의 크기는 작으므로, unique → cardinality 높음 → 선택도 높음
- 성별 field는 값이 두개이므로 기수성2, 주민번호는 모두 유니크한 값이므로 데이터의 개수만큼
선택도(selectivity)
- 데이터 집합에서 특정 값을 얼마나 잘 골라낼 수 있는지에 대한 지표다. (카디널리티 / 전체 데이터)
- 중복되는 값이 많을 수록(cardinality가 낮을 수록) 조회된 데이터가 많을 것이므로 선택도가 낮아지게 된다.

읽어야 하는 레코드의 건수

인덱스를 통해 도큐먼트를 읽는 것은 바로 도큐먼트를 읽는 것보다 5-6배의 고비용 작업이다.
인덱스를 통해 읽어야 하는 레코드가 전체의 15~20%를 넘으면, 옵티마이저는 인덱스를 이용하지 않고 풀스캔으로 필요한 레코드만 필터링해 처리하도록 유도한다.
- 힌트를 줘서 인덱스를 강제해도 성능상 이득이 없다.

B-Tree 인덱스를 통한 데이터 읽기

MongoDB는 어떻게 인덱스를 이용해서 도큐먼트를 읽어낼까?

인덱스 레인지 스캔

검색해야 할 인덱스의 범위가 결정된 경우를 레인지 스캔이라고 한다.
루트 노드 → 브랜치 노드 → 리프 노드 시작점을 찾아서 최종 결과까지 스캔한다.
- 이 과정을 인덱스 룩업이라 한다.
- B-Tree의 깊이만큼 랜덤 액세스가 필요하다.
리프 노드 시작 지점에서는 리프 노드 간 링크를 이용해(링크드 리스트) 리프 노드만 스캔한다.
- 스캔: 필요한 방향(오름차순 또는 내림차순)으로 인덱스를 읽어나감
실제 레코드를 가져오는 과정은 레코드 한건 별로 랜덤 I/O가 필요하기 때문에 인덱스를 통해 레코드를 읽는 작업이 비용이 많이 든다. 그래서 읽어야할 데이터가 전체의 15~20%를 넘으면 풀스캔이 효율적이다.

db.employees.find( {first_name: {$gt: "Ebbe", $lt: "Gad"}} )

db.users.createIndex( {score:1} )
db.users.find( {score: {$gte: 75, $lt: 95} )

인덱스 프리픽스 스캔

문자열, 날짜, 숫자를 대상으로 일부만 일치하는 패턴을 검색하고자할 때 사용하는 방법
레인지 스캔과 동일한 방식으로 작동한다. 필드 값 전체가 동일한지와 좌측부터 일치하는지 비교하는지의 차이

커버링 인덱스

db.users.createIndex( {sccore:1, name:1} )

db.users.find( {score: {$gte: 90}, {_id:0, name:1, gender:1} )
db.users.find( {score: {$gte: 90}, {_id:0, name:1} ) # 인덱스로 커버 가능

db.collection.find(query, projection)
컬렉션의 데이터 파일은 전혀 참조하지 않고 인덱스만 읽어서 쿼리가 처리되는 최적화
- 해당 쿼리를 인덱스 커버 쿼리라고 한다.
인덱스에서 원하는 키 엔트리를 찾고, 나머지 필드를 얻기 위해 나머지 정보가 저장된 도큐먼트를 읽는 작업은 상당한 성능 저하를 유발할 수 있다.

인덱스 인터섹션

하나의 컬렉션이 가진 두 개 이상의 인덱스를 검색해 결과를 만들고 교집합을 찾는 최적화 과정이다.
- OR 조건은 UNION 병합을 하기 때문에 AND 조건과 다름
실행 계획에서 AND_SORTED, AND_HASHED 스테이지가 있는지 확인하면 된다.
- AND_SORTED: RecordId가 정렬되어있다는 것을 가정하고 교집합만 뽑는 처리
- AND_HASHED: 일치 비교가 아닌 범위 비교는 정렬을 보장할 수 없으므로, 해시 조인을 함
효율적인 최적화가 아니어서 의도적으로 상황 만들려고 해도 실행 계획 만들기 쉽지 않을 것임
결국 하나의 컬렉션에서 데이터를 검색하는 최적의 방법은 컬렉션 별로 하나의 인덱스를 이용해 최소의 범위를 검색하는 것이다.

인덱스 풀 스캔

인덱스에 명시된 컬럼만으로 조건 또는 전체 쿼리를 처리할 수 있을 때 사용하는 방식
인덱스 전체 사이즈는 컬렉션 자체 사이즈보다 훨씬 작아 디스크 I/O를 적게 유발하기 때문
인덱스 리프 노드의 제일 앞 또는 뒤로 이동한 뒤 링크드 리스트를 따라 처음부터 끝까지 스캔
인덱스 레인지 스캔보다는 느리지만 컬렉션 풀 스캔보다는 효율적

Compound Index

2개 이상의 필드가 연결된 인덱스, Concatenated Index, Composite Index라고도 불린다.
인덱스의 N번째 컬럼은 N-1번째 컬럼이 같은 레코드 내에서 다시 정렬된다. 그래서 인덱스의 필드 순서가 상당히 중요하다. (예를 들어 gender | age 면 같은 gender 내에서 age가 정렬되는 것)
인덱스 간에 다른 정렬 방식을 가질 수 있으며, 별도 정렬 없이 인덱스만 읽어도 정렬 효과를 가질 수 있다.
서브 도큐먼트를 가지는 필드도 단일 필드로 취급되고, 서브도큐먼트도 인덱스에 추가할 수 있다.
오름차순으로 만들어진 인덱스는 B-Tree 왼쪽에 작은 값이 위치하고 오른 쪽에는 큰 값이 위치한다. 내림 차순은 반대
인덱스 생성 시 같은 필드에 대해 오름차순, 내림차순을 모두 생성할 필요는 없다.
- 인덱스 기본 정렬은 항상 오름차순이지만, 인덱스를 읽는 방향에 따라 오름차순 또는 내림차순의 효과를 얻을 수 있다.
범위를 결정해주는 조건이 많을 수록 쿼리 처리 성능을 높인다.
- 필터링 조건, 체크 조건: 범위를 제한하지 못하고 단순히 걸러주는 역할 → 많을 수록 느리게 만들 수 있다
  - dept_no은 비교 작업의 범위를 좁히는데 도움을 주지만, emp_no은 아니다.
```
  // dept_no, emp_no를 각각 순서를 바꿔 인덱스 두 개를 생성했다고 했을 때
  db.dept_emp.find( {[dept_no](http://dept.no/):"d002", emp_no:{$gte:10144}} )
```

예시

second 인덱스는 field1에 저장되는 값이 무엇이든 상관 없이 BSON으로 전환하고 바이트 배열 값으로 판단한다.

그래서 field1_1, field1_2의 순서가 변경되면 다른 바이트 배열이 되어 다른 값으로 인식한다.
second 인덱스에서는 두 개의 필드 값이 각각 인덱스 키 엔트리로 참여해, 순서 관계 없이 두 도큐먼트 모두 검색할 수 있다.

mongo> db.collection.createlndex( {"field1.field1_1" : 1, "field1.field1_2" : 1}, {name:"first" } )
mongo> db.collection.createlndex( {"field1" :1}, {name:"second"} )

mongo〉 db.collection.insert( {field1 :{field1_2:"ABC", field1_1:123}, field2:"2017-01-23"} )
mongo) db.collection.insert( {field1 :{field1_1:123, field1_2:"ABC"}, field2:"2017-01-23"} )

mongo〉db.collection.find( {field1:{field1_1:123, field1_2:"ABC"}} )
// 결과: first 인덱스는 둘 다 나오고, second 인덱스는 두 번째 insert 값만 나옴

서브 도큐먼트가 어떤 필드를 가지든 상관 없이 field1_1, field1_2의 조합만으로 컴파운드 인덱스가 생성됨.
first 인덱스를 쓰면 아래 도큐먼트도 함께 검색되지만, second를 쓰면 검색되지 않음

mongo> db.collection.insert({
  field1 : {field1_1 :123, field1_2:"2017-01-23", field1_3: "dummy"},
  field2: "2017-01-23" })

데이터 건수가 작은 경우 브랜치 노드가 없는 경우도 있다.
루트 노드, 리프 노드는 항상 존재한다.

인덱스의 가용성

B-Tree 인덱스는 왼쪽 값을 기준으로 오른쪽 값이 정렬되어 있다.
정렬이 검색의 기준이고, 첫 번째 인덱스를 모르고 두 번째 인덱스를 사용할 순 없다.
다음 조건으로는 인덱스를 작업 범위 결정 조건으로 사용할 수 없다.
- NOT-EQUAL로 비교된 경우 ($ne, $nin)
- 문자열 패턴 검색에서 프리픽스 일치가 아닌 경우
- 문자열 데이터타입의 콜레이션이 컬렉션이나 인덱스의 콜레이션과 다른 경우
사용 가능한 경우 (예시 370p)
- 첫 인덱스부터 동등한 형태( $eq, $in)로 비교되면서, 다음 연산자 중 하나로 비교
  - 동등 ($eq, $in)
  - 크다 작다 ($gt, $lt)
  - 문자열 패턴 좌측 일치 (/^검색어/)

PREVIOUSJPEG의 EOI 마커가 끝이 아닐 수 있다(!)

NEXTDB 인덱스란?