DB Index

• 조건을 만족하는 튜플들을 빠르게 조회, 정렬, 그룹핑하기 위해서는 인덱스를 사용해야 함
• 인덱스를 사용하기 위해서는 SQL에서 CREATE INDEX문 사용

SELECT * FROM player WHERE name = 'Sonny';
SELECT * FROM player WHERE team_id = 105 AND backnumber = 7;

CREATE INDEX player_name_idx ON player(name);
CREATE UNIQUE INDEX team_id_backnumber_idx ON player(team_id, backnumber);

-- 테이블 생성시 인덱스를 생성하려 하는경우는 아래와 같이 작성
CREATE TABLE player(
	id         INT         PRIMARY KEY,
    name       VARCHAR(20) NOT NULL,
    team_id    INT,
    backnumber INT,
    INDEX player_name_idx (name);
    UNIQUE INDEX team_id_backnumber_idx (team_id, backnumber)
);

• 테이블의 인덱스를 확인하고 싶으면 SHOW INDEX문 사용

SHOW INDEX FROM player;

• 인덱스를 생성하면 인덱스 값과 실제 튜플을 연결하는 포인터를 생성한 테이블을 통해 빠르게 데이터를 찾을 수 있음
• 쿼리의 조건이 여러개가 있을경우 하나만 인덱스가 걸려있을 경우 다른 값을 찾는데 속도가 느려짐으로, 두 값을 합친 인덱스를 순서를 맞춰 생성해야 함
• 쿼리가 어떤 인덱스를 사용하는지 확인하고자 하는 경우에는 쿼리 앞에 EXPLAIN을 사용하고, 인덱스를 명시하고자 하는 경우에는 USE INDEX문을 사용함

-- 사용하는 인덱스 확인
EXPLAIN
SELECT * FROM player WHERE backnumber = 7;
-- 직접 인덱스 지정
SELECT * FROM player USE INDEX(backnumber_idx)
WHERE backnumber = 7;

• 인덱스를 너무 많이 생성하면 write를 할 때마다 오버헤드가 발생하고, 저장공간을 더 많이 차지하게 됨에 주의
• 만약 인덱스만으로 쿼리를 처리할 수 있을 때에는 Covering index라 하며, 이 경우 조회 성능이 더 빨라짐
• 테이블에 데이터가 몇백건 정도로 적을 때, 조회하려는 데이터가 테이블의 상당 부분을 차지할 때는 Full Scan을 사용하는 것이 성능상 유리함
• 일반적으로 B Tree를 사용하며, 해시테이블로도 구현이 가능하나, rehashing 문제, range 비교 불가, 일부 attribute만의 조회 불가능등의 문제로 인해 잘 사용하지 않음

B tree

• B tree를 Binary search tree를 확장한 구조로, 노드에 2개 이상의 key를 오름차순으로 저장해 child node의 key값의 범위를 결정하는 tree를 의미함
• Binary search tree와 유사하면서도 자녀 노드의 최대 개수를 원하는대로 결정해서 쓸 수 있게 됨
• 최대 M개의 자녀를 가질 수 있는 B tree를 M차 B tree라 부르며, 이 때 각 노드의 최대 key의 수는 M - 1개가 되고, root, leaf 노드를 제외한 각 노드의 최소 자녀 노드 수는 celi(M / 2)개, root node를 제외한 각 노드의 최소 key 수는 celi(M / 2) - 1개가 됨
• B Tree에서는 자녀 노드의 key 수는 부모 노드의 key보다 하나가 더 많게 되며, 이로인해 B tree의 차수와는 상관없이 내부 노드에서는 최소 2개를 가지게 됨
• B Tree에 데이터를 추가할 때는 우선 leaf 노드에 값을 추가하고, 노드가 넘치게 되면 가운데 key를 기준으로 좌우 key를 분할하고, 가운데 키는 부모 노드로 올려주는 과정을 진행함
  이를 통해 B Tree는 leaf 노드들이 같은 레벨에 있는 Balanced tree를 유지할 수 있게 됨
• 데이터 삭제는 반드시 leaf 노드에서 진행되며, 노드의 key 수가 최소 key수보다 적어지면 트리를 재조정하게 됨
  • internal node가 있을 경우 leaf 노드 중 가장 근접한 값과 위치를 바꾸고 삭제해줌
  • key 수가 여유있는 형제가 있다면 이들에서 key를 가져오고, 아니면 부모의 지원을 받고 형제와 key를 합치게 됨
  • 만약 조정시에 문제가 있다면 다시 부모 노드부터 트리를 재조정함
• B tree는 조회, 삽입, 삭제의 시간복잡도는 전부 O(logN)으로, DB 인덱스에 사용됨
  • self-balanced-tree도 O(logN)인 것은 동일하지만, B tree가 차수가 높아질수록 트리의 깊이가 더 얕아지기 때문에 DB에서는 B tree가 성능상 더 유리함

출처:
https://www.youtube.com/watch?v=IMDH4iAQ6zM&list=PLcXyemr8ZeoREWGhhZi5FZs6cvymjIBVe&index=25
https://www.youtube.com/watch?v=IMDH4iAQ6zM&list=PLcXyemr8ZeoREWGhhZi5FZs6cvymjIBVe&index=26
https://www.youtube.com/watch?v=IMDH4iAQ6zM&list=PLcXyemr8ZeoREWGhhZi5FZs6cvymjIBVe&index=27
https://www.youtube.com/watch?v=IMDH4iAQ6zM&list=PLcXyemr8ZeoREWGhhZi5FZs6cvymjIBVe&index=28