1. SortedList는 데이터가 저장될 때마다 정렬을 수행해야하기 때문에 저장하는 과정을 복잡하지만 정렬이 이미 되어 있어 조회는 빠름
2. DBMS에서 인덱스도 많은 경우 INSERT, UPDATE, DELETE 문장의 처리가 느려지지만, SELECT문장은 빠르게 수행 가능
3. 결론적으로는 DBMS의 인덱스는 저장 성능을 희생하고 그 대신 데이터의 읽기 속도를 높이는 기능

1. 프라이머리 키(프라이머리 인덱스)
   1. 레코드를 대표하는 컬럼의 값으로 만들어진 인덱스로 Null과 중복을 허용하지 않음
2. 보조 키(세컨더리 인덱스)
   1. 프라이머리 키를 제외한 나머지 인덱스
   2. 유니크 인덱스는 프라이머리 인덱스를 대체가능하기 때문에 데체키라고도 불림

1. B-Tree알고리즘
   1. 칼럼의 값을 변형하지 않고 원래의 값을 이용해 인덱싱
   2. MySQL서버에서는 위치 기반 검색을 위한 R-Tree 인덱스 알고리즘도 있지만 B-Tree의 응용 알고리즘
2. Hash 인덱스 알고리즘
   1. 칼럼의 값으로 해시값을 계산해서 인덱싱하는 알고리즘으로 매우 빠른 검색을 지원
   2. 하지만, 컬럼값을 변형해서 인덱싱하므로 전방(prefix) 일치와 같은 일부, 범위 검색을 할때는 해시 인덱스를 사용할 수 없음

구조

1. 최상위에 root node가 존재하고 그 하위에 자식 노드가 붙은 형태
2. 가장 하위에 있는 노드를 leaf node라 하고, root node와 leaf node 사이에 있는 노드를 branch node라고 함
3. leaf node는 항상 실제 데이터 레코드를 찾아가기 위한 주소값을 가지고 있음
4. 예제에서 보이듯이 인덱스는 정렬되어 있는 상태이지만 실제 레코드는 임의의 순서대로 저장
5. 실제 레코드를 insert만 하는 경우 insert 순서대로 저장되지만, update, delete를 하는 경우 해당 빈자리를 새로운 insert가 매꾸기 때문에 insert순서 보장되지 않음
6. 세컨더리 인덱스
   1. MyISAM 테이블은 세컨더리 인덱스가 물리적인 주소를 가짐
   2. InnoDB 테이블은 프라이머리 키를 주소처럼 사용하기 때문에 논리적인 주소를 가짐
   3. 그래서 InnoDB 테이블에서 인덱스를 통해 읽을 때 데이터 파일을 바로 찾아가지 못함
   4. 인덱스에 저장되어 있는 프라이머리 키를 이용해 프라이머리 키를 조회한 후 프라이머리 키 인덱스의 리프 페이지에 있는 레코드를 읽음
   5. 각각 장단점을 가짐
7. 인덱스 키 추가
   1. 새로운 키 값이 저장될 때 새로운 키 값이 언제 등록될 지 모름
   2. B-Tree에 저장될 때는 키 값을 이용해 B-Tree상의 적절한 위치를 검색해야함(정렬을 위해)
   3. 저장될 위치가 결정되면 레코드의 키 값과 대상 레코드의 주소 정보를 B-Tree의 리프 노드에 저장
   4. 하지만 리프 노드의 페이지가 초과되는 경우 새로운 페이지로 분리해야하고 이를 브랜치 노드에도 반영해야 하므로 처리 범위가 넓어짐
   5. 이에 따라 B-Tree는 쓰기 작업에 비용이 많이 드는 편
8. 인덱스 키 삭제
   1. 삭제는 추가에 비해 간단함
   2. 해당 키 값이 저장된 B-Tree의 리프 노드를 찾아서 그냥 삭제 마크만 하면 작업이 완료
   3. 이렇게 삭제 마킹된 인덱스 키 공간은 계속 그대로 방치하거나 재사용 가능
9. 인덱스 키 변경
   1. 인덱스 키가 변경되면 인덱스가 저장될 리프 노드의 위치가 바뀌므로 단순히 인덱스상의 키 값만 변경하는 것은 불가
   2. B-Tree의 키 값 변경 작업은 먼저 키 값을 삭제한 후 다시 새로운 키 값을 추가하는 형태로 처리
10. 인덱스 키 검색
    1. 트리 탐색
       1. B-Tree루트 노드 → 브랜치 노드 → 리프 노드까지 이동하면서 인덱스를 검색하는 작업을 의미
       2. SELECT에서만 사용되는 것이 아니라, UPDATE/DELETE 를 처리하기 위해 레코드를 찾을 때도 사용
    2. B-Tree인덱스를 활용한 검색
       1. 100%일치하는 값을 찾을 때(등호 사용)
       2. 값의 앞부분만 일치하는 경우
       3. 부등호(범위)조건
       4. 값의 뒷부분의 일치를 찾는 경우 인덱스를 사용할 수 없음
       5. 또한 인덱스를 찾고자 하는 값을 변형(함수 사용)한 경우 인덱스를 사용할 수 없음
    3. InnoDB 테이블에서 지원하는 레코드 잠금, 넥스트 키락(갭락)이 검색을 수행한 인덱스를 잠근 후 테이블의 레코드를 잠그는 방식으로 구현
    4. 따라서 UPDATE/DELETE 문장이 실행될 때 테이블에 적절히 사용할 수 있는 인덱스가 없으면 불필요하게 많은 레코드를 잠그게 되며, 심지어 테이블의 모든 레코드를 잠글 수도 있음
11. 인덱스 사용에 영향을 미치는 요소
    1. B-Tree인덱스는 인덱스를 구성하는 칼럼의 크기, 레코드의 건수, 유니크한 인덱스 키 값의 개수 등에 의해 검색이나 변겨 작업의 성능이 영향을 받음
    2. 인덱스 키 값의 크기
       1. 페이지(블록)
          1. InnoDB엔진은 디스크에 데이터를 저장하는 가장 기본 단위를 페이지 또는 블록이라고 하며, 디스크의 모든 읽기 및 쓰기 작업의 최소 작업 단위가 된다.
          2. 또한 페이지는 InnoDB 스토리지 엔진의 버퍼 풀에서 데이터를 버퍼링하는 기본 단위가 되기도 한다.
          3. 인덱스도 결국은 페이지 단위로 관리됨
       2. 이진 트리구조는 각 노드가 자식 노드를 2개만 가지므로 B-Tree가 이진트리였다면 인덱스 검색이 상당히 비효율적임
       3. 일반적으로 DBMS의 B-Tree는 자식 노드의 개수가 가변적인 구조이며 이는 인덱스의 페이지 크기와 키 값의 크기에 따라 결정
       4. 5.7버전부터는 InnoDB 스토리지 엔진의 페이지 크기를 innodb_page_size 시스템 변수를 이용해 4~6KB 사이의 값을 선택할 수 있지만 기본값은 16KB
       5. 만약 인덱스 키가 커져서 페이지당 개수가 적어진다면 1개의 페이지를 참조하여 처리할 내용을 2~3개의 페이지를 참조하는 경우가 생김
    3. B-Tree 깊이
       1. B-Tree 인덱스의 깊이는 상당히 중요하지만 직접 제어는 불가능
       2. 보통 인덱스 키의 값이 커져서 페이지가 많아지는 경우 B-Tree의 깊이도 깊어짐
    4. 선택도(기수성)
       1. 모든 인덱스 키 값 가운데 유니크한 값의 수를 의미
       2. 인덱스 키 값 가운데 중복된 값이 많아지면 많아질수록 기수성, 선택성은 낮아짐
       3. 인덱스 관점에서는 기수성, 선택성이 높을수록 검색 대상이 줄어들기 때문에 고려해야함
       4. 예시 고려
          1. 10000건의 데이터를 가진 tb_test 테이블에서 WHERE에 2가지 조건을 통해 1건의 레코드를 찾는 상황
          2. 기수성이 1000인 경우
             1. 10000건 중에서 특정 조건에 맞는 컬럼은 10건이 되므로 10건이 조회됨
             2. 조회된 10건 중에서 조건에 맞는 하나의 레코드를 찾음
          3. 기수성이 10인 경우
             1. 10000건 중에서 특정 조건에 맞는 컬럼은 1000건이 되므로 1000건이 조회됨
             2. 조회된 1000건 중에서 조건에 맞는 하나의 레코드를 찾음
    5. 읽어야 하는 레코드의 건수
       1. 인덱스를 통해 읽어야 할 레코드의 건수(옵티마이저가 판단한 예상 건수)가 전체 테이블 레코드의 20~25%를 넘는 경우 인덱스를 활용하지 않는 것이 효율적
       2. 위 경우 모두 직접 읽어서 필요한 레코드만 가려내는(필터링) 방식으로 처리하는 것이 효율적
       3. 이처럼 많은 레코드를 읽을 때는 강제로 인덱스를 참조하도록 하더라도 성능상 이점이 없다는 것
12. B-Tree 인덱스를 통한 데이터 읽기
    1. 인덱스 레인지 스캔
       1. 인덱스 접근 방법 중 가장 대표적인 접근 방식
       2. 검색해야 하는 인덱스의 범위가 결정됐을 때 사용하는 방식
       3. 검색하려는 값의 수나 검색 결과 레코드 건수와 관계없이 레인지 스캔이라고 표현