어떻게 이진 검색을 데이터베이스 인덱싱에 사용합니까?

Question

이진 검색은 어떻게 작동하는지 알고 있지만 이진 검색에 대한 실질적인 사용법을 알고 싶습니다. 인터넷을 통해 검색 한 결과 주요 사용은 데이터베이스 인덱싱이지만 어떻게 이진 검색이 데이터베이스 색인 생성에 도움이되는지 이해할 수 없었습니다.

Answer 1

언제든지 정렬 된 목록이 있으면 이진 검색을 사용하여 효율적으로 목록을 검색 할 수 있습니다. 데이터베이스 인덱스는 정렬 된 데이터의 데이터 구조입니다.

Answer 2

Binary search을 사용하면 키가 이미 정렬되어 있다고 가정 할 때 해당 키로 레코드를 빠르게 찾을 수 있습니다. 키의 수가 많은 경우 특히 그렇습니다. 32 개의 키 읽기는 20 억 개의 정렬 된 키 집합 내에서 단일 고유 키를 찾는 데 충분합니다.

이진 검색은 각 검색 시도가 검색 할 레코드 수를 절반으로 줄이기 때문에이 방법으로 작동합니다.

즉, 데이터베이스는 일반적으로 b-trees 또는 red-black trees과 같은 다른 binary tree과 같은 데이터 구조를 사용하여 색인을 수행합니다. 이진 트리를 사용하면 검색하기 전에 키 목록을 정렬해야한다는 요구 사항이 제거됩니다.

Answer 3

내가 해결책을 찾고있을 때, 매우 유용한 링크를 찾았으며 귀하의 질문에 대한 대답을 찾았습니다.

Using Binary trees in Table Database indexes.

Answer 4

이진 검색은 각 단계에서 다음 위치 (중간 점)를 계산합니다.

DB의 이진 트리 미리 계산 단일 항목에 도달 할 때까지 각 단계의 중간 지점. 모든 중간 지점을 나무로 채 웁니다. 쿼리를 수행 할 때 DBMS는 트리를 조회합니다.