TIL 카테고리의 글은 그날 배운 것을 정리하는 목적으로 포스팅합니다. 내용이 잘못되었다면 댓글로 피드백 부탁드립니다.
대용량 데이터에서 사용자 ID 1,234,567번의 데이터를 어떻게 빠르게 얻을 수 있을까?
인덱스란
대용량 데이터에서 쉽게 원하는 데이터를 찾기위한 방법
원하는 위치까지 빠르게 도달하는 방법
- 사용자 정보를 고정 길이로 관리함
사용자 정보가 무조건 100바이트로 관리된다고 하면 사용자 ID * 100바이트 가 해당 사용자의 정보가 들어가있는 시작 위치가 됨. 1,234,567 사용자를 찾기 위해서도 1,234,567 * 100 을 하면 원하는 데이터를 빠르게 얻을 수 있음.
단 무조건 100바이트 값이기 때문에 100바이트 이상이 되는 데이터를 저장하지 못함. 그렇다고 넉넉하게 10000바이트로 한다고 하면 낭비가 너무 심함.
따라서 고정 길이 파일로 관리하는 방식은 좋지않음.
- 인덱스 구조 도입
고정 길이 방식이 아닌 가변 길이 방식으로 데이터를 관리함. 예를 들어 책의 색인처럼 키워드와 기재된페이지로 구성되어있도록.
소프트웨어 139쪽
이것을 응용하여 사용자 정보 데이터가 저장되는 곳가 별도로 사용자 ID(키워드)와 사용자 정보가 저장된 위치를 저장하는 파일을 만들어 사용자 정보를 빠르게 얻을 수 있음. 사용자 ID와 저장된 위치(주소)는 숫자로 관리하면 고정 길이로 취급할 수 있기 때문에 빠름.
이렇게 인덱스 구조를 도입하면 사용자 정보 데이터가 저장될 때 인덱스에도 새로운 데이터의 위치를 업데이트 해야하기 때문에 SELECT(검색)의 속도는 빨라지나 그 외 INSERT, UPDATE, DELETE 작업은 느려짐.
해시 인덱스
데이터의 키 값은 숫자가 아닌 문자열, 날짜가 될 수 도 있으므로 앞서 말했듯이 고정 길이로 취급하는게 어려울 때가 있음. 그래서 실제로는 키 값을 해시 함수에 대입해서 해시 값으로 저장하는 구조가 많이 사용됨. 해시는 문자열 길이에 상관 없이 동일한 크기이기때문에 고정 길이 포맷으로 대응할 수 있음. 해시 계산 비용도 O(1) 이므로 엄청 빠름!
하지만 해시 인덱스는 범위 검색에서는 뛰어나지 못함. id = 1인 데이터를 가져오는 것은 빠를 지 몰라도 created_at > 2019-01-02와 같은 범위 검색에선 사용할 수 없음.
아래 목적에서는 사용 불가능
price < 10000title LIKE 'FIMAL%'ORDER BY created_at DESC
**해시 인덱스는 많은 검색 작업에서 단지 일부 용도에서만 빠르게 처리할 수 있음. **
B+Tree 인덱스
나무 구조로 되어있는 인덱스. 정상에 있는 블록이 ROOT 블록 , 최하층이 Leaf 블록, 중간에 있는 Branch 블록.
루트 블록과 브랜치 블록은 검색의 키인 사용자 ID에 대해 해당 블록이 어디에 있는지 정보를 가지고 있음. 최하층의 리프 블록에는 실제 데이터의 저장 위치의 정보를 가지고 있음.
인덱스 검색 시 루트 -> 브랜치 -> 리프 순으로 도달해 원하는 데이터를 얻을 수 있음.
레코드 수가 적으면 루트와 리프만 있는 패턴도 존재함. 레코드수가 많으면 브랜치 아래에 브랜치가 들어가있는 4계층 이상의 구성이 될 수 도 있음.
최적화
- 고유성 보장하기
- 인덱스는 고유성을 보증하기 위한 목적으로 사용가능함. 해시 인덱스는 동일한 ID의 경우 동일한 해시 값이 되고 B+Tree 인덱스에선 동일 리프에 도달하기 때문에 적은 코스트로 쉽게 중복체크가 가능함. 따라서 고유성을 보장하려는 열(PK, Unique key)에 인덱스를 지정하는 것이 좋음. (필수로 되어있기도 함)
- 멀티 칼럼 인덱스
- 여러개의 조건을 지정해 검색하고 싶은 경우를 위해 여러 조건의 인덱스를 걸어 검색을 가속화 할 수 있는데 이것을 멀티 칼럼 인덱스라고 함.
- Index only read
COUNT()함수와 같이 레코드의 값이 아닌 레코드 개수를 구하고 싶은 경우에는 인덱스만 읽어서 결과를 구할 수 있음. 데이터 영역을 읽지 않고 인덱스 영역만 읽어 처리를 빠르게 할 수 있음.
refer
웹 프로그래머를 위한 데이터베이스를 지탱하는 기술