데이터베이스 필드에 인덱스를 추가하면 해당 필드를 검색하는 속도가 빨라지는 이유는 무엇입니까?

Question

저는 데이터베이스에 익숙하지 않고 검색해야하는 필드에 인덱스를 추가하면 검색 시간이 크게 단축 될 수 있다는 점을 읽었습니다. 나는이 현실을 이해하지만 그것이 실제로 어떻게 작동하는지 궁금하다. 나는이 주제에 대해 조금 연구했지만, 어떻게 작동하는지에 대한 기술적 인 대답이 아니라 선명하고 간결한 것을 발견하지 못했다.

필자는 책 뒤쪽의 색인과 비슷한 비유를 읽었지만 고유 한 요소 (예 : 사용자 데이터베이스의 전자 메일 주소)의 데이터 필드의 경우에는 백 도서 비유의 경우 인덱스되지 않은 검색과 동일한 선형 검색 시간을 제공합니다.

검색 시간을 크게 단축하기 위해 여기에서 진행되는 작업은 무엇입니까? B+-Trees을 사용하여 검색하는 방법에 대해 조금 읽었지만 설명이 너무 많습니다. 내가 찾고있는 것은 무엇이 진행되고 있는지, 기술적 세부 사항이 아닌 개념적으로 이해하는 데 도움이되는 내용을 간략하게 살펴 보는 것입니다.

Answer 1

연구 및 토론의 조금 후, 여기에 내가 배운 무엇을 좋아 :

는 개념적으로 인덱스가 정렬되지 않은 그것은 각 인덱스 값 포인트를 원래의 IT 인덱싱되는 데이터 필드의 정렬 사본 (이다) 행. 데이터베이스는 값의 정렬 방법을 알고 있기 때문에 처음부터 끝까지 값을 찾는 것보다 더 정교한 검색 알고리즘을 적용 할 수 있습니다. binary search algorithm은 정렬 된 목록에 대한 검색 알고리즘의 간단한 예이며 최대 검색 시간을 O (n)에서 O (log n)으로 줄입니다.

참고 사항 : 알맞은 정렬 알고리즘은 일반적으로 O (n log n)을 사용합니다. 이는 이전에 들었던 것처럼 자주 검색 할 필드에만 색인을 붙여야 함을 의미합니다. 전체 검색을 몇 번 수행하는 것보다 정렬을 포함하는 색인을 추가하는 것이 약간 비쌉니다. 예를 들어,> 1,000,000 개 이상의 큰 데이터베이스의 경우 한 번 검색하는 것보다 정렬하는 것이 20 배 더 비싸다.

편집 : 특히 디스크 작업에서 읽기와 관련하여 검색 효율성을 자세히 조사하려면 @Jarod Elliott의 answer을 참조하십시오.

Answer 2

해당 요소가 순으로 페이지가 인 경우 색인없는 검색과 동일한 검색 시간이 될 수 있습니다. 예.

그러나 귀하의 도서가 저자가 주문한 도서 리뷰 목록이지만 ISBN을 알고 있다면 어떻게 될까요? ISBN은 독특합니다. 그렇지만 찾고자하는 것을 찾으려면 각 리뷰를 스캔해야합니다.

이제 ISBN으로 정렬 된 책 뒷면에 색인을 추가하십시오. 붐, 빠른 검색 시간. 이는 인덱스 키 (ISBN)에서 실제 데이터 행 (이 경우 책의 페이지 번호)으로 이동하는 데이터베이스 인덱스와 유사합니다.

Answer 3

검색 알고리즘 효율성을 확장하면 데이터베이스 성능의 핵심 영역은 데이터 액세스 속도입니다. 일반적으로 디스크에서 데이터를 읽는 것은 메모리에서 데이터를 읽는 것보다 훨씬 느립니다.

요점을 설명하기 위해 모든 것이 디스크에 저장되어 있다고 가정합니다. 필드의 특정 값을 찾는 테이블의 모든 데이터 행을 검색해야하는 경우 디스크에서 전체 데이터 행을 읽어야 일치하는지 확인해야합니다.이를 일반적으로 '테이블 스캔이라고합니다 '.

테이블이 100MB라면 디스크에서 읽어야 할 100MB입니다.

검색 할 열을 간단하게 색인화하면 색인에는 데이터의 고유 한 값과 해당하는 전체 데이터 행의 정확한 위치에 대한 참조가 저장됩니다. 이 색인은 이제 전체 표의 100MB와 비교하여 10MB 일 수 있습니다.

디스크에서 10MB의 데이터를 읽는 것 (그리고 각 일치에 대해 전체 행 데이터를 읽는 데 약간의 추가 비용)은 100MB를 읽는 것보다 약 10 배 빠릅니다.

다른 데이터베이스는 이러한 작업을 훨씬 빠르게 수행 할 수 있도록 여러 가지 방법으로 인덱스 또는 데이터를 메모리에 저장합니다. 그러나 데이터 세트가 크고 메모리에 맞지 않으면 디스크 속도가 큰 영향을 줄 수 있으며 인덱싱을 통해 엄청난 이득을 볼 수 있습니다. 메모리에 여전히 많은 성능 향상이있을 수 있습니다 (다른 효율성 중에서도).

일반적으로 메모리에 쉽게 맞는 작은 데이터 세트를 인덱싱하는 것과 눈에 띄는 차이가 없음을 알 수 있습니다.

기본 세부 사항은 시스템에 따라 다르며 실제로는 훨씬 더 복잡하지만 실제로 디스크를 읽는 대 메모리가이를 설명하는 이해하기 쉬운 방법을 읽는 것으로 나타났습니다.