<div id="readability-page-1" class="page"><div><h2 id="8장-인덱스">8장 인덱스</h2>
<h2 id="81-디스크-읽기-방식">8.1 디스크 읽기 방식</h2>
<ul>
<li>데이터베이스 성능 튜닝은 디스크 I/O를 줄이는게 관건</li>
</ul>
<h3 id="811-하드-디스크-드라이브hdd와-솔리드-스테이트-드라이브ssd">8.1.1 하드 디스크 드라이브(HDD)와 솔리드 스테이트 드라이브(SSD)</h3>
<ul>
<li>HDD(DB 서버 병목 초래) 대체를 위한 SSD</li>
<li>HDD와 같은 인터페이스(SATA, SAS) 지원 → 내장디스크, DAS, SAN에 사용 가능<ul>
<li>참고: <a href="https://cheershennah.tistory.com/168">https://cheershennah.tistory.com/168</a></li>
</ul></li>
<li>SSD는 랜덤 I/O 작업이 HDD보다 훨씬 빠르기 때문에 DBMS용 스토리지에 좋음</li>
</ul>
<h3 id="812-랜덤-io와-순차-io">8.1.2 랜덤 I/O와 순차 I/O</h3>
<ul>
<li>랜덤 I/O: HDD 플래터를 돌려서 읽어야 할 데이터가 저장된 위치로 디스크 헤더를 이동시킨 다음 데이터를 읽는 것<ul>
<li>순차 I/O와 다르게 페이지 당 시스템 콜 요청</li>
<li>부하가 큼 → MySQL 서버에는 그룹커밋, 바이너리 로그 버퍼, InnoDB 로그 버퍼 등 기능 내장</li>
<li>실제는 RAID 컨트롤러 캐시 메모리가 효율적 I/O 처리 도움<ul>
<li><a href="https://12bme.tistory.com/286">https://12bme.tistory.com/286</a></li>
</ul></li>
</ul></li>
<li>쿼리 튜닝으로 랜덤 I/O → 순차 I/O 하기는 쉽지 않음, 일반적으로 쿼리 튜닝하는 것은 랜덤 I/O 자체를 줄여주는 것이 목적(쿼리를 처리하는 데 꼭 필요한 데이터만 읽도록 쿼리를 개선)</li>
</ul>
<h2 id="82-인덱스란">8.2 인덱스란?</h2>
<ul>
<li>찾아보기: 인덱스 / 책 내용: 데이터 파일</li>
<li>인덱스를 통해 데이터 파일에 저장된 레코드 주소를 알아낼 수 있음<ul>
<li>칼럼 값(key) - 레코드 저장된 주소(value)로 인덱스 만들기</li>
</ul></li>
<li>책처럼 DBMS의 인덱스도 컬럼 값을 미리 정렬해서 보관</li>
<li>SortedList: 저장되는 값을 항상 정렬된 상태로 유지하는 자료구조 - 인덱스<ul>
<li>데이터가 저장될 때마다 항상 값을 정렬해야 하므로 저장하는 과정이 복잡하고 느리지만, 이미 정렬돼 있어서 아주 빨리 원하는 값을 찾아올 수 있음 → SELECT는 빠르지만 인덱스가 많은 테이블은 INSERT나 UPDATE 그리고 DELETE 문장의 처리가 느려짐</li>
<li>SELECT WHERE 조건절에 사용된다고 다 인덱스 걸면 저장 성능 망함</li>
</ul></li>
<li>ArrayList: 값을 저장되는 순서대로 그대로 유지하는 자료구조 - 데이터 파일</li>
<li>Primary Key: 레코드를 대표하는 컬럼 값으로 만들어진 인덱스</li>
<li>Secondary key: primary 제외한 모든 인덱스</li>
<li>B-Tree 알고리즘: 가장 많이씀, 컬럼의 값을 변형하지 않고, 원래의 값을 이용해 인덱싱하는 알고리즘</li>
<li>Hash 인덱스 알고리즘: 컬럼의 값으로 해시 값을 계산해서 인덱싱하는 알고리즘, 매우 빠른 검색을 지원, 값을 변형해서 인덱싱하므로, 전방(Prefix) 일치와 같이 값의 일부만 검색하고자 할 때는 해시 인덱스를 사용할 수 없음, 메모리 기반 DB에서 많이 사용</li>
<li>Unique: 레코드 1건 찾으면 더 안 찾아도 되는 걸 옵티마이저에게 알려줌</li>
</ul>
<h2 id="83-b-tree-인덱스">8.3 B-Tree 인덱스</h2>
<ul>
<li>일반적으로 DBMS에서는 주로 B+-Tree 또는 B*-Tree 사용<ul>
<li>B(Balanced)</li>
</ul></li>
<li>컬럼의 원래 값을 변형시키지 않고, 인덱스 구조체 내에서는 항상 정렬된 상태로 유지</li>
</ul>
<h3 id="831-구조-및-특성">8.3.1 구조 및 특성</h3>
<ul>
<li>root node + branch node + leaf node</li>
<li>leaf node: 실제 데이터 레코드를 찾아가기 위한 주솟값 보유</li>
<li>인덱스의 키값은 정렬돼 있지만 데이터 파일의 레코드는 임의의 순서대로 저장<ul>
<li>레코드가 중간에 삭제되어 빈 공간이 생기면 다음 INSERT는 빈 공간 활용하기 때문에 데이터 파일의 레코드 != INSERT된 순서임</li>
<li>InnoDB 레코드는 클러스터되어 디스크에 저장되기 때문에 PK 순서로 저장됨<ul>
<li><a href="https://dev.mysql.com/doc/refman/5.7/en/innodb-index-types.html">https://dev.mysql.com/doc/refman/5.7/en/innodb-index-types.html</a></li>
<li>다른 db는 선택인데 이노 친구는 디폴트로 클러스터링 테이블 생성함</li>
</ul></li>
</ul></li>
<li>인덱스는 테이블의 키 컬럼만 가지고 있으므로 나머지 컬럼을 읽으려면 데이터 파일에서 해당 레코드를 찾아야 함 → 리프 노드가 데이터 파일에 저장된 레코드의 주소 갖는 이유</li>
<li>8.5(MyISAM): PK값과 무관하게 insert 순서대로 레코드가 데이터 파일에 저장 → ROWID라는 물리적 주솟값 가짐 → 인덱스가 데이터 파일에 저장된 레코드의 ROWID 값을 포인터로 가짐 (ROWID=secondary index)</li>
<li>8.6(InnoDB): PK=ROWID 역할=논리적 주소 → 인덱스에 저장된 PK(11800)로 프라이머리 키 루트노드 인덱스 키에 맵핑된 자식노드 주소를 타고타고 가 리프 노드에 있는 레코드를 읽는다.<ul>
<li>secondary index(Aamer)가 PK(11800)를 바라보고 있음</li>
<li>PK 저장하고 있는 B-Tree 다시 위에서부터 보면서 11800번 찾음<ul>
<li>1번 시나리오<ul>
<li>11800어딨을까~</li>
<li>11043? 나 너보다 큰데~ 브랜치 노드로 감</li>
<li>11800? 오~ 찾음~ 레코드로 감</li>
</ul></li>
<li>2번 시나리오<ul>
<li>10128 어딨을까~</li>
<li>루트노드 봤더니 없네~ 10057 보단 큰데 11043보다는 작네~</li>
<li>또 10057이네~ 내가 이것보단 큰데~ 10418보다는 작네~</li>
<li>오 리프노드 10128 드디어있네~</li>
</ul></li>
</ul></li>
<li>즉 Inno에서는 PK 검색 아니면 PK B-Tree 인덱스 다시 타줘야 한다.</li>
<li><a href="http://www.btechsmartclass.com/data_structures/b-trees.html">http://www.btechsmartclass.com/data_structures/b-trees.html</a></li>
</ul></li>
</ul>
<h3 id="832-b-tree-인덱스-키-추가-및-삭제">8.3.2 B-Tree 인덱스 키 추가 및 삭제</h3>
<h4 id="8321-인덱스-키-추가">8.3.2.1 인덱스 키 추가</h4>
<ul>
<li>바로 저장 → B-Tree상의 적절한 위치를 검색</li>
<li>저장될 위치가 결정되면 레코드의 키값과 대상 레코드의 주소 정보를 B-Tree의 리프 노드에 저장</li>
<li>리프노드 꽉차면 분리해야되는데 비용 많이 든다 → B-Tree 쓰기 작업 비용 많이 드는 이유<ul>
<li>비용 계산? 대충 레코드 추가:인덱스에 키 추가=1:1.5</li>
<li>요 작업 MyISAM/MeMory 스토리지 엔진은 INSERT와 동시에 하는데, InnoDB는 똑똑해서 지연시킬 수 있음(PK, UK는 중복체크해야해서 즉시 반영)</li>
</ul></li>
</ul>
<h4 id="8322-인덱스-키-삭제">8.3.2.2 인덱스 키 삭제</h4>
<ul>
<li>키 값이 저장된 B-Tree의 리프 노드를 찾아서 삭제 표시</li>
<li>요것도 InnoDB는 체인지 버퍼로 지연 처리 가능</li>
</ul>
<h4 id="8323-인덱스-키-변경">8.3.2.3 인덱스 키 변경</h4>
<ul>
<li>Balanced Tree라 했지? → 변경하고 싶으면 바꿔치기 안되고 키 값 삭제한 후 새로 추가해야함(키 값으로 리프노드 위치 발란싱하니까)</li>
<li>요것도 InnoDB는 체인지 버퍼로 지연 처리 가능</li>
</ul>
<h4 id="8324-인덱스-키-검색">8.3.2.4 인덱스 키 검색</h4>
<ul>
<li>인덱스 검색 = 빠른 검색을 위함 = 트리 탐색이라고 함</li>
<li>SELECT에서만 사용하는 것이 아니라 UPDATE, DELETE 처리하기 위해 레코드를 먼저 검색해야 할 경우에도 사용</li>
<li>B-Tree 인덱스는 100% 일치 또는 값의 앞부분만 일치하는 경우에만 사용 가능</li>
<li>인덱스 키 값 변형된 이후 비교하면 빠른 검색 사용 불가 (B-Tree에 변한건 없으니까 당연)</li>
<li>InnoDB 테이블에서 지원하는 레코드 잠금 &amp; 넥스트 키 락(갭 락) → 검색을 수행한 인덱스를 잠근 후 테이블의 레코드를 잠그기 때문에 불필요하게 많은 레코드가 잠길 수 있음</li>
</ul>
<h3 id="833-b-tree-인덱스-사용에-영향을-미치는-요소">8.3.3 B-Tree 인덱스 사용에 영향을 미치는 요소</h3>
<ul>
<li>인덱스를 구성하는 칼럼의 크기</li>
<li>레코드의 건수</li>
<li>유니크한 인덱스 키값의 개수</li>
</ul>
<h4 id="8331-인덱스-키-값의-크기">8.3.3.1 인덱스 키 값의 크기</h4>
<ul>
<li>페이지/블록: InnoDB 스토리지 엔진에서 디스크에 데이터를 저장하는 가장 기본 단위<ul>
<li>페이지는 InnoDB 스토리지 엔진의 버퍼 풀에서 데이터를 버퍼링하는 기본 단위이기도 함</li>
<li>루트/브랜치/리프 노드 애들도 결국 다 페이지임</li>
</ul></li>
<li>B-Tree 자식노드 수는 인덱스의 페이지 크기와 키 값의 크기에 따라 결정<ul>
<li>페이지 당 저장할 수 있는 인덱스 키 수만큼 레코드 가져올 수 있음</li>
<li>키 값의 크기가 커지면 디스크로부터 여러번 읽어야하고 느려짐</li>
</ul></li>
</ul>
<h4 id="8332-b-tree-깊이">8.3.3.2 B-Tree 깊이</h4>
<ul>
<li>인덱스 키 값이 증가 → 페이지에 당 인덱스 키 수 감소 → b-tree 깊이 증가 → 디스크 읽기 횟수 증가</li>
</ul>
<h4 id="8333-선택도기수성">8.3.3.3 선택도(기수성)</h4>
<ul>
<li>Cardinality = the number of cardinal (basic) members in a set</li>
<li>Selectivity = Cardinality / Total Number Of Records</li>
<li>인덱스의 유니크한 값의 수 → 인덱스나 쿼리의 성능을 결정(교재 country index 예시 참고)</li>
</ul>
<h4 id="8334-읽어야하는-레코드의-건수">8.3.3.4 읽어야하는 레코드의 건수</h4>
<ul>
<li>손익분기점 잘 판단해야<ul>
<li>전체 테이블의 모두 읽어서 필요 없는 50만 건을 버리는 것이 효율적일지, 인덱스를 통해 필요한 50건만 읽어 오는 것이 효율적인지 판단</li>
<li>(DBMS 옵티마이저 왈) 인덱스 1건 = 직접 * 4~5</li>
<li>인덱스 타는 레코드 수가 전체의 20~25% 넘으면 직접 가져와서 필터링하는게 더 효율적</li>
</ul></li>
</ul>
<h3 id="834-b-tree-인덱스를-통한-데이터-읽기">8.3.4 B-Tree 인덱스를 통한 데이터 읽기</h3>
<h4 id="8341-인덱스-레인지-스캔">8.3.4.1 인덱스 레인지 스캔</h4>
<ul>
<li>제일 빠름</li>
<li>검색해야할 인덱스의 범위가 결정됐을 때 사용하는 방식</li>
<li>시작 위치(인덱스 탐색) 찾은 후 리프노드 간 링크를 통해 다음 리프노드를 찾아 스캔(인덱스 스캔)</li>
<li>최종 범위(Gad)에 다다르면 멈추고 결과 반환</li>
<li>어떤 방식으로 스캔하든 관계 없이, 해당 인덱스를 수정하는 칼럼의 정순 또는 역순으로 정렬된 상태로 레코드를 가져옴</li>
<li>인덱스의 리프 노드에서 검색 조건에 맞는 것들을 데이터 파일에서 레코드를 읽어오는 과정이 필요<ul>
<li>데이터 레코드 당 랜덤 I/O 한 번씩 발생</li>
<li>커버링 인덱스(쿼리를 충족하는데 필요한 모든 데이터를 갖는 인덱스) 사용 시 디스크 레코드 안 읽어도 된다.<ul>
<li><a href="https://tecoble.techcourse.co.kr/post/2021-10-12-covering-index/">https://tecoble.techcourse.co.kr/post/2021-10-12-covering-index/</a></li>
</ul></li>
</ul></li>
</ul>
<h4 id="8342-인덱스-풀-스캔">8.3.4.2 인덱스 풀 스캔</h4>
<ul>
<li>인덱스의 처음부터 끝까지 모두 읽는 방식</li>
<li>쿼리의 조건절에 사용된 컬럼이 인덱스의 첫 번째 컬럼이 아닌 경우 발생<ul>
<li>인덱스는 (A,B,C) 칼럼의 순서대로 만들어져 있지만 쿼리의 조건절에 B 칼럼이나 C 칼럼으로 검색하는 경우</li>
</ul></li>
<li>과정<ul>
<li>인덱스 리프 노드의 처음 또는 끝으로 이동한 후 리프노드를 연결하는 LinkedList 탐색(인덱스 레인지 스캔보단 느리지만 테이블 풀스캔보단 빠름)</li>
</ul></li>
</ul>
<h4 id="8343-루스-인덱스-스캔">8.3.4.3 루스 인덱스 스캔</h4>
<ul>
<li>느슨하게 또는 듬성듬성 하게 인덱스를 읽는 것</li>
<li>인덱스 레인지 스캔과 비슷하게 동작하지만, 중간마다 필요치 않은 인덱스 키 값은 스킵</li>
<li>GROUP BY 또는 집합 함수 가운데 MAX(), MIN() 함수에 대해 최적화에 사용</li>
</ul>
<h4 id="8344-인덱스-스킵-스캔">8.3.4.4 인덱스 스킵 스캔</h4>
<ul>
<li>MySQL 8.0부터 옵티마이저가 인덱스 두번째 칼럼으로도 인덱스 타게 해줌</li>
<li>이게 바로 인덱스 스킵 스캔</li>
<li>이전에는 두 번째 칼럼만 where 조건 걸면 인덱스 풀스캔했음(type=index)</li>
<li>EXPLAIN 찍어보면 지금은 type=range + Extra에 스킵 스캔 나옴</li>
<li>제약 사항<ul>
<li>where 조건절에 안 써준 인덱스 앞에 걸린 컬럼의 유니크한 수가 적어야 함</li>
<li>커버링 인덱스여야함(인덱스 존재하는 컬럼만으로 쿼리 완성)</li>
</ul></li>
</ul>
<h3 id="835-다중-칼럼multi-column-인덱스">8.3.5 다중 칼럼(Multi-column) 인덱스</h3>
<ul>
<li>두 개 이상의 칼럼으로 구성된 인덱스</li>
<li>두번째 컬럼은 첫 번째 칼럼에 의존해서 정렬</li>
<li>따라서 인덱스 내 컬럼 위치가 중요</li>
</ul>
<h3 id="836-b-tree-인덱스의-정렬-및-스캔-방향">8.3.6 B-Tree 인덱스의 정렬 및 스캔 방향</h3>
<ul>
<li>인덱스를 어느 방향으로 읽을지는 쿼리에 따라서 옵티마이저가 실시간으로 만들어내는 실행 계획에 따라 결정</li>
</ul>
<h4 id="8361-인덱스의-정렬">8.3.6.1 인덱스의 정렬</h4>
<ul>
<li>MySQL 8.0부터 혼합 정렬 인덱스 사용 가능</li>
</ul>
<h5 id="83611-인덱스-스캔-방향">8.3.6.1.1 인덱스 스캔 방향</h5>
<ul>
<li>옵티마이저가 똑똑해서 인덱스 걸어둔 컬럼에 대해서 정렬하면 가까운 곳에서부터 정순/역순 스캔함</li>
</ul>
<h5 id="83612-내림차순-인덱스">8.3.6.1.2 내림차순 인덱스</h5>
<ul>
<li>복합인덱스에서 내림/올림 혼합되면 8.0이 지원하는 내림차순 인덱스만 사용 가능</li>
</ul>
<pre><code><span>CREATE</span> <span>INDEX</span> ix_teamname_userscore <span>ON</span> employees <span>(</span>team_name <span>ASC</span><span>,</span> User_score <span>DESC</span><span>)</span><span>;</span></code></pre>
<ul>
<li>만약 한 컬럼을 역순으로 정렬해야하는데 하나는 인덱스 오름차순으로 생성/나머지는 내림차순으로 생성한다면?</li>
</ul>
<pre><code>SELECT * FROM t1 ORDER BY tid ASC LIMIT 12619775, 1;
SELECT * FROM t1 ORDER BY tid DESC LIMIT 12619775, 1;</code></pre>
<ul>
<li>12619775번부터 1건 반환해야하는데 역순 정렬 쿼리가 정순 정렬 쿼리보다 28.9% 시간이 더 걸림</li>
<li>왜? InnoDB 엔진에서 페이지 잠금이 forward index scan에 더 적합한 구조를 가져서</li>
<li>페이지 내부 레코드가 단방향 링크만 가진다. (페이지 간은 doubly인데 안에가 single linked list임)<ul>
<li>물리적으로 정렬된게 아니라 페이지 구조가 Heap처럼 연결되어 있는것</li>
</ul></li>
</ul>
<h3 id="837-b-tree-인덱스의-가용성과-효율성">8.3.7 B-Tree 인덱스의 가용성과 효율성</h3>
<h4 id="8371-비교-조건의-종류와-효율성">8.3.7.1 비교 조건의 종류와 효율성</h4>
<ul>
<li>다중 컬럼 인덱스에서 각 컬럼의 순서 &amp; 컬럼에 사용된 조건에 따라 인덱스 컬럼 활용 형태가 달라짐</li>
</ul>
<pre><code><span>SELECT</span> <span>*</span> <span>FROM</span> dept_emp <span>WHERE</span> dept_no<span>=</span><span>'d002'</span> <span>AND</span> emp_no <span>&gt;=</span><span>10144</span><span>;</span></code></pre>
<ul>
<li>INDEX (dept_no, emp_no)<ul>
<li>dept_no가 d002고 emp_no가 10144 이상인 레코드를 찾은 후 그 d002 끝까지 읽으면 된다.</li>
<li>dept_no='d002' AND emp_no &gt;=10144: 작업 범위 결정 조건</li>
</ul></li>
<li>INDEX (emp_no, dept_no)<ul>
<li>emp_no가 10144인 레코드를 찾은 후 dept_no 적합성을 전부 검증해줘야 한다. (필터링)</li>
<li>다중컬럼인덱스 정렬방식 때문(N번째 키값은 N-1번째 키 값에 의해 다시 정렬됨</li>
<li>dept_no='d002': 필터링 조건(체크 조건), emp_no: 작업 범위 결정 조건</li>
<li>작업범위 결정 조건은 많을수록 성능에 유리하지만 체크 조건은 많아도 쿼리 성능을 높이지 못함</li>
</ul></li>
</ul>
<h4 id="8372-인덱스의-가용성">8.3.7.2 인덱스의 가용성</h4>
<ul>
<li>B-Tree 인덱스는 왼쪽값 기준으로 오른쪽값이 정렬됨</li>
<li>왼쪽 키 값이 없으면 인덱스 레인지 스캔이 불가</li>
</ul>
<pre><code><span>SELECT</span> <span>*</span> <span>FROM</span> employees <span>WHERE</span> first_name <span>LIKE</span> <span>'%mer'</span><span>;</span></code></pre>
<ul>
<li>LIKE 쿼리 왼쪽부분이 고정되지 않았기 때문에 B-tree 인덱스 효과 X</li>
</ul>
<pre><code><span>SELECT</span> <span>*</span> <span>FROM</span> dept_emp <span>WHERE</span> emp_no<span>&gt;=</span><span>10144</span><span>;</span></code></pre>
<ul>
<li>dept_no 조건이 없기 때문에 다중컬럼 인덱스 제대로 못탄다.</li>
<li>Left-most 정렬 규칙은 GROUP BY, ORDER BY 절에도 동일하게 적용</li>
</ul>
<h4 id="8373-가용성과-효율성-판단">8.3.7.3 가용성과 효율성 판단</h4>
<ul>
<li>아래 조건들일 경우 인덱스를 작업 범위 결정 조건으로 사용 불가(체크 조건으로만 사용)<ul>
<li>NOT-EQUAL로 비교</li>
<li>LIKE '%??'(뒷부분 일치)</li>
<li>스토어드 함수나 다른 연산자로 인덱스 컬럼이 변형</li>
<li>NOT-DETERMINISTIC 속성의 스토어드 함수가 비교조건에 사용</li>
<li>데이터 타입이 서로 다른 비교</li>
<li>문자열 데이터 타입의 콜레이션이 다를 때</li>
</ul></li>
<li>일반적인 DBMS에서는 Null 값이 인덱스에 저장되지 않지만 MySQL에서는 저장됨<ul>
<li>작업 범위 결정 조건으로 인덱스 사용</li>
</ul></li>
</ul>
<pre><code><span>.</span><span>.</span> <span>WHERE</span> <span>column</span> <span>IS</span> <span>NULL</span> <span>.</span><span>.</span></code></pre></div></div>

janeljs.log

8장 인덱스
8.1 디스크 읽기 방식
데이터베이스 성능 튜닝은 디스크 I/O를 줄이는게 관건
8.1.1 하드 디스크 드라이브(HDD)와 솔리드 스테이트 드라이브(SSD)
HDD(DB 서버 병목 초래) 대체를 위한 SSD
HDD와 같은 인터페이스(SATA, SAS) 지원 → 내장디스크, DAS, SAN에 사용 가능
참고: https://cheershennah.tistory.com/168
SSD는 랜덤 I/O 작업이 HDD보다 훨씬 빠르기 때문에 DBMS용 스토리지에 좋음
8.1.2 랜덤 I/O와 순차 I/O
랜덤 I/O: HDD 플래터를 돌려서 읽어야 할 데이터가 저장된 위치로 디스크 헤더를 이동시킨 다음 데이터를 읽는 것
순차 I/O와 다르게 페이지 당 시스템 콜 요청
부하가 큼 → MySQL 서버에는 그룹커밋, 바이너리 로그 버퍼, InnoDB 로그 버퍼 등 기능 내장
실제는 RAID 컨트롤러 캐시 메모리가 효율적 I/O 처리 도움
https://12bme.tistory.com/286
쿼리 튜닝으로 랜덤 I/O → 순차 I/O 하기는 쉽지 않음, 일반적으로 쿼리 튜닝하는 것은 랜덤 I/O 자체를 줄여주는 것이 목적(쿼리를 처리하는 데 꼭 필요한 데이터만 읽도록 쿼리를 개선)
8.2 인덱스란?
찾아보기: 인덱스 / 책 내용: 데이터 파일
인덱스를 통해 데이터 파일에 저장된 레코드 주소를 알아낼 수 있음
칼럼 값(key) - 레코드 저장된 주소(value)로 인덱스 만들기
책처럼 DBMS의 인덱스도 컬럼 값을 미리 정렬해서 보관
SortedList: 저장되는 값을 항상 정렬된 상태로 유지하는 자료구조 - 인덱스
데이터가 저장될 때마다 항상 값을 정렬해야 하므로 저장하는 과정이 복잡하고 느리지만, 이미 정렬돼 있어서 아주 빨리 원하는 값을 찾아올 수 있음 → SELECT는 빠르지만 인덱스가 많은 테이블은 INSERT나 UPDATE 그리고 DELETE 문장의 처리가 느려짐
SELECT WHERE 조건절에 사용된다고 다 인덱스 걸면 저장 성능 망함
ArrayList: 값을 저장되는 순서대로 그대로 유지하는 자료구조 - 데이터 파일
Primary Key: 레코드를 대표하는 컬럼 값으로 만들어진 인덱스
Secondary key: primary 제외한 모든 인덱스
B-Tree 알고리즘: 가장 많이씀, 컬럼의 값을 변형하지 않고, 원래의 값을 이용해 인덱싱하는 알고리즘
Hash 인덱스 알고리즘: 컬럼의 값으로 해시 값을 계산해서 인덱싱하는 알고리즘, 매우 빠른 검색을 지원, 값을 변형해서 인덱싱하므로, 전방(Prefix) 일치와 같이 값의 일부만 검색하고자 할 때는 해시 인덱스를 사용할 수 없음, 메모리 기반 DB에서 많이 사용
Unique: 레코드 1건 찾으면 더 안 찾아도 되는 걸 옵티마이저에게 알려줌
8.3 B-Tree 인덱스
일반적으로 DBMS에서는 주로 B+-Tree 또는 B*-Tree 사용
B(Balanced)
컬럼의 원래 값을 변형시키지 않고, 인덱스 구조체 내에서는 항상 정렬된 상태로 유지
8.3.1 구조 및 특성
root node + branch node + leaf node
leaf node: 실제 데이터 레코드를 찾아가기 위한 주솟값 보유
인덱스의 키값은 정렬돼 있지만 데이터 파일의 레코드는 임의의 순서대로 저장
레코드가 중간에 삭제되어 빈 공간이 생기면 다음 INSERT는 빈 공간 활용하기 때문에 데이터 파일의 레코드 != INSERT된 순서임
InnoDB 레코드는 클러스터되어 디스크에 저장되기 때문에 PK 순서로 저장됨
https://dev.mysql.com/doc/refman/5.7/en/innodb-index-types.html
다른 db는 선택인데 이노 친구는 디폴트로 클러스터링 테이블 생성함
인덱스는 테이블의 키 컬럼만 가지고 있으므로 나머지 컬럼을 읽으려면 데이터 파일에서 해당 레코드를 찾아야 함 → 리프 노드가 데이터 파일에 저장된 레코드의 주소 갖는 이유
8.5(MyISAM): PK값과 무관하게 insert 순서대로 레코드가 데이터 파일에 저장 → ROWID라는 물리적 주솟값 가짐 → 인덱스가 데이터 파일에 저장된 레코드의 ROWID 값을 포인터로 가짐 (ROWID=secondary index)
8.6(InnoDB): PK=ROWID 역할=논리적 주소 → 인덱스에 저장된 PK(11800)로 프라이머리 키 루트노드 인덱스 키에 맵핑된 자식노드 주소를 타고타고 가 리프 노드에 있는 레코드를 읽는다.
secondary index(Aamer)가 PK(11800)를 바라보고 있음
PK 저장하고 있는 B-Tree 다시 위에서부터 보면서 11800번 찾음
1번 시나리오
11800어딨을까~
11043? 나 너보다 큰데~ 브랜치 노드로 감
11800? 오~ 찾음~ 레코드로 감
2번 시나리오
10128 어딨을까~
루트노드 봤더니 없네~ 10057 보단 큰데 11043보다는 작네~
또 10057이네~ 내가 이것보단 큰데~ 10418보다는 작네~
오 리프노드 10128 드디어있네~
즉 Inno에서는 PK 검색 아니면 PK B-Tree 인덱스 다시 타줘야 한다.
http://www.btechsmartclass.com/data_structures/b-trees.html
8.3.2 B-Tree 인덱스 키 추가 및 삭제
8.3.2.1 인덱스 키 추가
바로 저장 → B-Tree상의 적절한 위치를 검색
저장될 위치가 결정되면 레코드의 키값과 대상 레코드의 주소 정보를 B-Tree의 리프 노드에 저장
리프노드 꽉차면 분리해야되는데 비용 많이 든다 → B-Tree 쓰기 작업 비용 많이 드는 이유
비용 계산? 대충 레코드 추가:인덱스에 키 추가=1:1.5
요 작업 MyISAM/MeMory 스토리지 엔진은 INSERT와 동시에 하는데, InnoDB는 똑똑해서 지연시킬 수 있음(PK, UK는 중복체크해야해서 즉시 반영)
8.3.2.2 인덱스 키 삭제
키 값이 저장된 B-Tree의 리프 노드를 찾아서 삭제 표시
요것도 InnoDB는 체인지 버퍼로 지연 처리 가능
8.3.2.3 인덱스 키 변경
Balanced Tree라 했지? → 변경하고 싶으면 바꿔치기 안되고 키 값 삭제한 후 새로 추가해야함(키 값으로 리프노드 위치 발란싱하니까)
요것도 InnoDB는 체인지 버퍼로 지연 처리 가능
8.3.2.4 인덱스 키 검색
인덱스 검색 = 빠른 검색을 위함 = 트리 탐색이라고 함
SELECT에서만 사용하는 것이 아니라 UPDATE, DELETE 처리하기 위해 레코드를 먼저 검색해야 할 경우에도 사용
B-Tree 인덱스는 100% 일치 또는 값의 앞부분만 일치하는 경우에만 사용 가능
인덱스 키 값 변형된 이후 비교하면 빠른 검색 사용 불가 (B-Tree에 변한건 없으니까 당연)
InnoDB 테이블에서 지원하는 레코드 잠금 & 넥스트 키 락(갭 락) → 검색을 수행한 인덱스를 잠근 후 테이블의 레코드를 잠그기 때문에 불필요하게 많은 레코드가 잠길 수 있음
8.3.3 B-Tree 인덱스 사용에 영향을 미치는 요소
인덱스를 구성하는 칼럼의 크기
레코드의 건수
유니크한 인덱스 키값의 개수
8.3.3.1 인덱스 키 값의 크기
페이지/블록: InnoDB 스토리지 엔진에서 디스크에 데이터를 저장하는 가장 기본 단위
페이지는 InnoDB 스토리지 엔진의 버퍼 풀에서 데이터를 버퍼링하는 기본 단위이기도 함
루트/브랜치/리프 노드 애들도 결국 다 페이지임
B-Tree 자식노드 수는 인덱스의 페이지 크기와 키 값의 크기에 따라 결정
페이지 당 저장할 수 있는 인덱스 키 수만큼 레코드 가져올 수 있음
키 값의 크기가 커지면 디스크로부터 여러번 읽어야하고 느려짐
8.3.3.2 B-Tree 깊이
인덱스 키 값이 증가 → 페이지에 당 인덱스 키 수 감소 → b-tree 깊이 증가 → 디스크 읽기 횟수 증가
8.3.3.3 선택도(기수성)
Cardinality = the number of cardinal (basic) members in a set
Selectivity = Cardinality / Total Number Of Records
인덱스의 유니크한 값의 수 → 인덱스나 쿼리의 성능을 결정(교재 country index 예시 참고)
8.3.3.4 읽어야하는 레코드의 건수
손익분기점 잘 판단해야
전체 테이블의 모두 읽어서 필요 없는 50만 건을 버리는 것이 효율적일지, 인덱스를 통해 필요한 50건만 읽어 오는 것이 효율적인지 판단
(DBMS 옵티마이저 왈) 인덱스 1건 = 직접 * 4~5
인덱스 타는 레코드 수가 전체의 20~25% 넘으면 직접 가져와서 필터링하는게 더 효율적
8.3.4 B-Tree 인덱스를 통한 데이터 읽기
8.3.4.1 인덱스 레인지 스캔
제일 빠름
검색해야할 인덱스의 범위가 결정됐을 때 사용하는 방식
시작 위치(인덱스 탐색) 찾은 후 리프노드 간 링크를 통해 다음 리프노드를 찾아 스캔(인덱스 스캔)
최종 범위(Gad)에 다다르면 멈추고 결과 반환
어떤 방식으로 스캔하든 관계 없이, 해당 인덱스를 수정하는 칼럼의 정순 또는 역순으로 정렬된 상태로 레코드를 가져옴
인덱스의 리프 노드에서 검색 조건에 맞는 것들을 데이터 파일에서 레코드를 읽어오는 과정이 필요
데이터 레코드 당 랜덤 I/O 한 번씩 발생
커버링 인덱스(쿼리를 충족하는데 필요한 모든 데이터를 갖는 인덱스) 사용 시 디스크 레코드 안 읽어도 된다.
https://tecoble.techcourse.co.kr/post/2021-10-12-covering-index/
8.3.4.2 인덱스 풀 스캔
인덱스의 처음부터 끝까지 모두 읽는 방식
쿼리의 조건절에 사용된 컬럼이 인덱스의 첫 번째 컬럼이 아닌 경우 발생
인덱스는 (A,B,C) 칼럼의 순서대로 만들어져 있지만 쿼리의 조건절에 B 칼럼이나 C 칼럼으로 검색하는 경우
과정
인덱스 리프 노드의 처음 또는 끝으로 이동한 후 리프노드를 연결하는 LinkedList 탐색(인덱스 레인지 스캔보단 느리지만 테이블 풀스캔보단 빠름)
8.3.4.3 루스 인덱스 스캔
느슨하게 또는 듬성듬성 하게 인덱스를 읽는 것
인덱스 레인지 스캔과 비슷하게 동작하지만, 중간마다 필요치 않은 인덱스 키 값은 스킵
GROUP BY 또는 집합 함수 가운데 MAX(), MIN() 함수에 대해 최적화에 사용
8.3.4.4 인덱스 스킵 스캔
MySQL 8.0부터 옵티마이저가 인덱스 두번째 칼럼으로도 인덱스 타게 해줌
이게 바로 인덱스 스킵 스캔
이전에는 두 번째 칼럼만 where 조건 걸면 인덱스 풀스캔했음(type=index)
EXPLAIN 찍어보면 지금은 type=range + Extra에 스킵 스캔 나옴
제약 사항
where 조건절에 안 써준 인덱스 앞에 걸린 컬럼의 유니크한 수가 적어야 함
커버링 인덱스여야함(인덱스 존재하는 컬럼만으로 쿼리 완성)
8.3.5 다중 칼럼(Multi-column) 인덱스
두 개 이상의 칼럼으로 구성된 인덱스
두번째 컬럼은 첫 번째 칼럼에 의존해서 정렬
따라서 인덱스 내 컬럼 위치가 중요
8.3.6 B-Tree 인덱스의 정렬 및 스캔 방향
인덱스를 어느 방향으로 읽을지는 쿼리에 따라서 옵티마이저가 실시간으로 만들어내는 실행 계획에 따라 결정
8.3.6.1 인덱스의 정렬
MySQL 8.0부터 혼합 정렬 인덱스 사용 가능
8.3.6.1.1 인덱스 스캔 방향
옵티마이저가 똑똑해서 인덱스 걸어둔 컬럼에 대해서 정렬하면 가까운 곳에서부터 정순/역순 스캔함
8.3.6.1.2 내림차순 인덱스
복합인덱스에서 내림/올림 혼합되면 8.0이 지원하는 내림차순 인덱스만 사용 가능
CREATE INDEX ix_teamname_userscore ON employees (team_name ASC, User_score DESC);
만약 한 컬럼을 역순으로 정렬해야하는데 하나는 인덱스 오름차순으로 생성/나머지는 내림차순으로 생성한다면?
SELECT * FROM t1 ORDER BY tid ASC LIMIT 12619775, 1;
SELECT * FROM t1 ORDER BY tid DESC LIMIT 12619775, 1;
12619775번부터 1건 반환해야하는데 역순 정렬 쿼리가 정순 정렬 쿼리보다 28.9% 시간이 더 걸림
왜? InnoDB 엔진에서 페이지 잠금이 forward index scan에 더 적합한 구조를 가져서
페이지 내부 레코드가 단방향 링크만 가진다. (페이지 간은 doubly인데 안에가 single linked list임)
물리적으로 정렬된게 아니라 페이지 구조가 Heap처럼 연결되어 있는것
8.3.7 B-Tree 인덱스의 가용성과 효율성
8.3.7.1 비교 조건의 종류와 효율성
다중 컬럼 인덱스에서 각 컬럼의 순서 & 컬럼에 사용된 조건에 따라 인덱스 컬럼 활용 형태가 달라짐
SELECT * FROM dept_emp WHERE dept_no='d002' AND emp_no >=10144;
INDEX (dept_no, emp_no)
dept_no가 d002고 emp_no가 10144 이상인 레코드를 찾은 후 그 d002 끝까지 읽으면 된다.
dept_no='d002' AND emp_no >=10144: 작업 범위 결정 조건
INDEX (emp_no, dept_no)
emp_no가 10144인 레코드를 찾은 후 dept_no 적합성을 전부 검증해줘야 한다. (필터링)
다중컬럼인덱스 정렬방식 때문(N번째 키값은 N-1번째 키 값에 의해 다시 정렬됨
dept_no='d002': 필터링 조건(체크 조건), emp_no: 작업 범위 결정 조건
작업범위 결정 조건은 많을수록 성능에 유리하지만 체크 조건은 많아도 쿼리 성능을 높이지 못함
8.3.7.2 인덱스의 가용성
B-Tree 인덱스는 왼쪽값 기준으로 오른쪽값이 정렬됨
왼쪽 키 값이 없으면 인덱스 레인지 스캔이 불가
SELECT * FROM employees WHERE first_name LIKE '%mer';
LIKE 쿼리 왼쪽부분이 고정되지 않았기 때문에 B-tree 인덱스 효과 X
SELECT * FROM dept_emp WHERE emp_no>=10144;
dept_no 조건이 없기 때문에 다중컬럼 인덱스 제대로 못탄다.
Left-most 정렬 규칙은 GROUP BY, ORDER BY 절에도 동일하게 적용
8.3.7.3 가용성과 효율성 판단
아래 조건들일 경우 인덱스를 작업 범위 결정 조건으로 사용 불가(체크 조건으로만 사용)
NOT-EQUAL로 비교
LIKE '%??'(뒷부분 일치)
스토어드 함수나 다른 연산자로 인덱스 컬럼이 변형
NOT-DETERMINISTIC 속성의 스토어드 함수가 비교조건에 사용
데이터 타입이 서로 다른 비교
문자열 데이터 타입의 콜레이션이 다를 때
일반적인 DBMS에서는 Null 값이 인덱스에 저장되지 않지만 MySQL에서는 저장됨
작업 범위 결정 조건으로 인덱스 사용
.. WHERE column IS NULL ..

[Real MySQL 8.0] 8장 인덱스

댓글