데이터베이스에서 쿼리 검색을위한 알고리즘은 무엇입니까?

Question

안녕하세요 여러분, 현재 검색 알고리즘 최적화에 대한 연구를하고 있습니다.

현재로서는 데이터베이스에 대해 연구 중입니다.

SQL 지원이있는 데이터베이스에서.

특정 테이블에 대한 쿼리를 작성할 수 있습니다.

1. 표 1에서 번호 선택에서 Name = "Test";
2. Select *에서 Table1 여기서 Name = "Test";

1은 이름이 Test 인 곳에서 Table1의 번호를 검색하고 2는 이름이 Test 인 모든 열을 검색합니다.

나는 함수의 개념을 이해하지만 검색의 접근법을 배우는 데 관심이있는 것은 무엇입니까?

첫 번째 인덱스부터 n 번째 인덱스까지 조건이 참이므로 속도가 O (n) 일 때만 잡아 당길 것인가 아니면 속도가 빨라지는 고유 한 알고리즘을 가지고 있는가? 보통

는 DBMS 테이블을 정렬합니다 SELECT 쿼리에서 seacrh을 수행 할 수

Answer 1

아주 좋은 질문, 그러나 테이블의 구조에 따라 많은 답변을 가질 수 있고 어떻게 정규화는 (은 머지 소트를 사용 이 알고리즘은 디스크의 입출력에 좋으며 quicksort가 아님) 인덱스에 따라 (테이블에있는 경우) 숫자와 일치하지만 구조가 복잡하면 DBMS가 트리에서 검색을 수행 할 수 있지만 너무 깊어서, 나는 내 노트에서 다시 연구하도록하겠습니다.

SQL Server 2008에서 쿼리 실행 계획 here is an example을 활성화하는 방법을 권장합니다. 그런 다음 WHERE 절을 사용하여 SELECT 문을 실행하면 DBMS 내부에서 진행되는 작업을 이해할 수 있습니다.

Answer 2

색인이없는 경우 선형 검색이 수행됩니다.

그러나 데이터베이스는 일반적으로 열을 키로 지정할 때 B Tree 색인을 사용합니다. 이들은 자기 디스크 하드웨어에서 잘 수행 할 수 있도록 특수하게 조정 된 특수 데이터 구조 형식입니다 (높은 B 트리 분기 요소). 가장 중요한 시간이 소요되는 요소는 탐색 작업입니다 (자기 헤드가 파일의 diff 부분으로 이동해야 함).).

인덱스는 열에있는 값의 정렬 된/구조화 된 복사본이라고 생각할 수 있습니다. 검색중인 값이 색인에 있는지 빠르게 판별 할 수 있습니다. 발견되면 주 데이터 파일에서 해당 행의 정확한 위치를 다시 가리키는 포인터를 찾습니다 (행에서 다른 열로 이동하여 읽을 수 있음). 때로는 다중 열 인덱스가 쿼리에서 요청한 모든 데이터를 포함하고 있으며 주 파일로 건너 뛸 필요가 없으며 발견 된 내용과 완료된 내용을 읽을 수 있습니다.

다른 유형의 색인이 있지만 아이디어를 얻은 것 같습니다. 데이터를 복제하고 검색 속도가 빠른 방식으로 정렬하십시오.

큰 데이터베이스에서 인덱스는 복잡한 쿼리가 완료 될 때까지 몇 분의 1 초를 기다리는 것과 차이가있을 수 있습니다.

btw- B 트리는 간단하고 이해하기 쉬운 데이터 구조가 아니며 탐색 알고리즘도 복잡합니다. 또한 데이터베이스에서 디스크의 데이터 청크를 디스크에서 지속적으로로드/언로드하고 메모리에서 관리하기 때문에 탐색하는 대부분의 코드보다 추악합니다. 그러면 코드가 현저하게 손상됩니다. 그러나 만약 당신이 binary search trees에 익숙하다면, 당신은 그 개념을 충분히 이해하고 있다고 생각합니다.

Answer 3

음, 데이터 저장 방법 및 수행하려는 작업에 따라 다릅니다.

• 이미 표시된 바와 같이, 항목을 유지하기위한 공통 구조는 B+ tree입니다. 트리는 실제 데이터가 리프에만 저장되고 키가 내부 노드에 저장되므로 디스크에 맞게 최적화됩니다. 상위 k 레벨의 트리를 RAM에 저장할 수 있기 때문에 대개 매우 적은 수의 디스크 액세스 만 허용하며 몇 개의 하위 레벨 만 디스크에 저장되어 각각에 대해 디스크 읽기가 필요합니다.
• 다른 대안은 hash table입니다. 메모리 (RAM)에 "포인터"배열을 유지합니다.이 포인터는 해당 해시 값이있는 모든 항목을 포함하는 버킷을 포함하는 디스크 주소를 나타냅니다. 이 방법을 사용하면 O(1) 디스크 액세스 만 필요합니다 (데이터베이스 처리시 일반적으로 병목 현상이 발생 함). 따라서 비교적 빠른 속도 여야합니다.
  그러나 해시 테이블에서는 효율적인 범위 쿼리 (B + 트리에서 효율적으로 수행 할 수 있음)를 허용하지 않습니다.

위의 모든 단점은 하나의 키가 필요하다는 것입니다. 즉 해시 테이블이나 B + 트리가 관계의 필드 "id"에 따라 작성된 다음 "key "- 쓸모 없게된다.
관계의 모든 필드를 빠르게 검색하려면 여러 가지 구조가 필요하며 각 구조는 다른 키에 따라 다르므로 매우 효율적이지 않습니다.

이제는 특정 용도에 따라 여러 가지 최적화를 고려해야합니다. 예를 들어 검색 수가 매우 적을 것으로 예상되면 (예 : 총 로그 작업의 로그 로그 N이 더 작음) B + 트리를 유지하는 것이 전반적으로 덜 효율적이어서 목록을 검색하는 경우와 드문 경우로 요소를 저장하는 것입니다. 선형 검색.