인덱스란

허정·2022년 7월 2일

1. 인덱스란

데이터베이스의 테이블에 대한 검색 속도를 향상시켜주는 자료구조입니다. (검색을 위해) 임의의 규칙대로 부여된, 임의의 대상을 가리키는 무언가라고 할 수 있습니다.

인덱스는 데이터베이스의 탐색 성능을 좌우합니다.
데이터 저장, 수정, 삭제에 대한 성능을 희생시켜 탐색에 대한 성능을 대폭 상승하는 방식입니다.
테이블의 특정 Column에 인덱스를 생성하면, 해당 column의 데이터를 정렬한 후, 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장됩니다.
column의 값과 물리적 주소를 key-value 쌍으로 저장합니다.

일정 시간 내의 검색 속도를 내기 위해서는 B-Tree를 사용해야 합니다.

테이블을 검색하는 속도와 성능이 향상
시스템의 전반적인 부하를 줄임
핵심은 인덱스에 의해 데이터들이 정렬된 형태를 갖는다는 것
기존의 Where문으로 특정 조건의 데이터를 찾기 위해서 테이블의 전체를 조건과 비교해야 하는 "Full Table Scan" 작업이 필요했는데, 인덱스를 이용하면 데이터들이 정렬되어 있기 때문에 조건에 맞는 데이터를 빠르게 찾을 수 있습니다.

인덱스를 항상 정렬된 상태로 유지해야 하기 때문에 인덱스가 적용된 column에 INSERT, DELETE, UPDATE 작업을 수행하면 다음의 추가 작업이 필요합니다.
INSERT: 새로운 데이터에 대한 인덱스를 추가
DELETE: 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업을 수행
UPDATE: 기존의 인덱스를 사용하지 않음 처리, 갱신된 데이터에 대한 인덱스 추가

해시 테이블은 key value를 한 쌍으로 데이터를 저장하는 자료구조입니다. 해시 충돌이라는 변수가 존재하지만 평균적으로 O(1)의 매우 빠른 시간만에 원하는 데이터를 탐색할 수 있는 구조입니다.

일정 시간 내의 검색 속도를 내기 위해서는 B-Tree를 사용해야 합니다.
INSERT, UPDATE, DELETE 작업이 자주 발생하지 않는 column에 사용하는 것이 좋습니다. 특히 DELETE가 자주 발생하지 않아야 합니다.
인덱스에 대한 key 값이 있습니다. 무엇을 기준으로 할지에 대한 것입니다.
B+Tree 가 B-Tree의 단점을 개선시킨 자료구조는 아닙니다. 왜냐하면, 검색속도나 접근성을 높이는 것은 있으나, 업데이트 시키거나 자료를 하나라도 지우면 분리해집니다.
File System에서 사용하는 자료구조는 B-Tree입니다.
컴퓨터 System S/W에서 Kernel이라고 불리는 애들 중에는, Kernel이라는 말을 쓰는 것은 2가지입니다.
OS, DB
데이터는 파일의 형태로 저장되어 있습니다.
인덱스는 결국 "빠른 검색 + 무엇을 모르는가를 판단"이 핵심입니다.
선형 검색이 아쉬운 것은 6이 없는데도 사진상의 데이터 6개를 모두 뒤져야한다는 것입니다. 그래야 6이 없다는 것을 알 수 있습니다.
이것을 비선형 자료구조로 접근하면 쉽게 해결할 수 있습니다.

5보다 작은 애들을 찾아달라는 조건을 걸어봅시다. 추가로 내림차순으로 정렬해달라는 조건이 붙었습니다.
인덱스는 RAM 메모리에 있고, Data는 파일이니까 HDD에 있습니다.
5의 왼쪽을 선택해서 정렬하면 됩니다.
그러면 쉽게 1 - 3 - 4로 정렬을 할 수 있습니다.
그러면 이제 선형 리스트를 만들게 됩니다.
index로부터 선형 리스트를 추출하게 됩니다.
선형 리스트도 RAM 메모리에 들어가게 됩니다.
조건을 찾는 구문이 SELECT 입니다. FIND가 아닌 이유는 어떤 인덱스에서 조건에 맞는 정보들을 추출, 즉 선택하는 것입니다. 그렇게 해서 쉽게 선형구조로 접근이 가능하게 만들어 줍니다.