헤이 하브르! 나는 기사의 번역을 당신의 관심에 제시합니다
"관계형 데이터베이스는 어떻게 작동하나요?".

관계형 데이터베이스에 관해서는 뭔가 빠졌다고 생각하지 않을 수 없습니다. 그들은 어디에서나 사용됩니다. 작고 유용한 SQLite부터 강력한 Teradata까지 다양한 데이터베이스를 사용할 수 있습니다. 그러나 데이터베이스 작동 방식을 설명하는 기사는 몇 개뿐입니다. "howdoesarelationaldatabasework"를 사용하여 직접 검색하면 결과가 얼마나 적은지 확인할 수 있습니다. 게다가 이 글들은 짧습니다. 최신 기술(BigData, NoSQL 또는 JavaScript)을 찾고 있다면 해당 기술의 작동 방식을 설명하는 더 자세한 기사를 찾을 수 있습니다.

관계형 데이터베이스는 대학 과정, 연구 논문 및 서적 외부에서 설명하기에는 너무 오래되고 지루합니까?

개발자로서 저는 이해하지 못하는 것을 사용하는 것을 싫어합니다. 그리고 데이터베이스가 40년 이상 사용되었다면 반드시 이유가 있을 것입니다. 수년에 걸쳐 저는 제가 매일 사용하는 이 이상한 블랙박스를 진정으로 이해하기 위해 수백 시간을 보냈습니다. 관계형 데이터베이스 매우 흥미로운 이유는 그들이 유용하고 재사용 가능한 개념을 기반으로. 데이터베이스를 이해하는 데 관심이 있지만 이 광범위한 주제를 자세히 알아볼 시간이나 의향이 없었다면 이 기사를 읽어 보세요.

이 글의 제목은 노골적이지만, 이 문서의 목적은 데이터베이스 사용 방법을 이해하는 것이 아닙니다.. 그러므로, 간단한 연결 요청과 기본 쿼리를 작성하는 방법을 이미 알고 있어야 합니다. 크루드; 그렇지 않으면 이 글을 이해하지 못할 수도 있습니다. 당신이 알아야 할 것은 그것뿐입니다. 나머지는 제가 설명하겠습니다.

알고리즘의 시간 복잡도(BigO)와 같은 몇 가지 컴퓨터 과학 기초부터 시작하겠습니다. 여러분 중 일부가 이 개념을 싫어한다는 것을 알고 있지만, 이것이 없이는 데이터베이스 내부의 복잡성을 이해할 수 없습니다. 워낙 큰 주제이기 때문에, 나는 집중할 것이다 내가 중요하다고 생각하는 것: 데이터베이스가 처리되는 방식 SQL 요청. 그냥 소개할게요 기본 데이터베이스 개념기사가 끝나면 내부적으로 무슨 일이 일어나고 있는지 알 수 있습니다.

이 글은 많은 알고리즘과 데이터 구조를 포함하는 길고 기술적인 글이므로 시간을 내어 끝까지 읽어보시기 바랍니다. 일부 개념은 이해하기 어려울 수 있습니다. 건너뛰어도 일반적인 아이디어를 얻을 수 있습니다.

더 많은 지식을 갖고 있는 분들을 위해 이 기사는 3개 부분으로 나누어져 있습니다.

• 하위 수준 및 상위 수준 데이터베이스 구성 요소 개요
• 쿼리 최적화 프로세스 개요
• 트랜잭션 및 버퍼 풀 관리 개요

기본으로 돌아가기

몇 년 전(멀고 먼 은하계에서...) 개발자는 자신이 코딩하는 작업 수를 정확히 알아야 했습니다. 그들은 느린 컴퓨터의 CPU와 메모리를 낭비할 여유가 없었기 때문에 알고리즘과 데이터 구조를 마음 속으로 알고 있었습니다.

이 부분에서는 데이터베이스를 이해하는 데 필수적인 이러한 개념 중 일부를 상기시켜 드리겠습니다. 컨셉도 소개할게요 데이터베이스 인덱스.

O(1) 대 O(n2)

요즘에는 많은 개발자들이 알고리즘의 시간 복잡도에 관심을 두지 않습니다. 그리고 그들의 말이 맞습니다!

그러나 많은 양의 데이터(수천 개를 말하는 것이 아닙니다)를 다루거나 밀리초 단위로 어려움을 겪고 있다면 이 개념을 이해하는 것이 중요합니다. 그리고 여러분이 상상할 수 있듯이 데이터베이스는 두 가지 상황을 모두 처리해야 합니다! 나는 요점을 전달하는 데 필요한 것보다 더 많은 시간을 소비하게 만들지 않을 것입니다. 이는 나중에 비용 기반 최적화의 개념을 이해하는 데 도움이 될 것입니다(비용 기반으로 최적화).

개념

알고리즘의 시간 복잡도 주어진 양의 데이터에 대해 알고리즘이 완료되는 데 걸리는 시간을 확인하는 데 사용됩니다.. 이러한 복잡성을 설명하기 위해 우리는 big O 수학적 표기법을 사용합니다. 이 표기법은 주어진 입력 수에 대해 알고리즘이 필요한 작업 수를 설명하는 함수와 함께 사용됩니다.

예를 들어, "이 알고리즘의 복잡성은 O(some_function())입니다"라고 말하면 해당 알고리즘이 특정 양의 데이터를 처리하려면 some_function(a_certain_amount_of_data) 작업이 필요하다는 의미입니다.

이 경우, 중요한 것은 데이터의 양이 아닙니다**, 그렇지 않으면 ** 데이터 양이 증가함에 따라 작업 수가 어떻게 증가하는지. 시간 복잡도는 정확한 작업 수를 제공하지 않지만 실행 시간을 추정하는 좋은 방법입니다.

이 그래프에서는 다양한 유형의 알고리즘 시간 복잡성에 대한 작업 수와 입력 데이터 양을 확인할 수 있습니다. 나는 그것들을 표시하기 위해 로그 눈금을 사용했습니다. 즉, 데이터의 양이 1억에서 1억으로 빠르게 증가한다는 것을 알 수 있습니다.

• O(1) 또는 상수 복잡도는 일정하게 유지됩니다(그렇지 않으면 상수 복잡도라고 부르지 않습니다).
• O(기록(n)) 수십억 개의 데이터가 있어도 여전히 낮은 수준.
• 최악의 난이도 - O(n2), 연산 수가 급격히 증가하는 경우.
• 다른 두 가지 합병증도 마찬가지로 빠르게 증가합니다.

예

데이터 양이 적을 경우 O(1)과 ​​O(n2)의 차이는 무시할 수 있습니다. 예를 들어, 2000개의 요소를 처리해야 하는 알고리즘이 있다고 가정해 보겠습니다.

• O(1) 알고리즘을 사용하면 작업 비용이 1회 발생합니다.
• O(log(n)) 알고리즘에는 7개의 작업 비용이 듭니다.
• O(n) 알고리즘에는 2개의 작업 비용이 듭니다.
• O(n*log(n)) 알고리즘에는 14개의 작업 비용이 듭니다.
• O(n2) 알고리즘에는 4개의 작업 비용이 듭니다.

O(1)과 ​​O(n2)의 차이는 커 보이지만(4만 연산) 눈을 깜박일 시간인 최대 2ms를 잃게 됩니다. 실제로 최신 프로세서는 다음을 처리할 수 있습니다. 초당 수억 건의 작업. 이것이 바로 많은 IT 프로젝트에서 성능과 최적화가 문제가 되지 않는 이유입니다.

앞서 말했듯이, 엄청난 양의 데이터를 다룰 때는 이 개념을 아는 것이 여전히 중요합니다. 이번에 알고리즘이 1개의 요소를 처리해야 하는 경우(데이터베이스의 경우 그다지 많지 않음):

• O(1) 알고리즘을 사용하면 작업 비용이 1회 발생합니다.
• O(log(n)) 알고리즘에는 14개의 작업 비용이 듭니다.
• O(n) 알고리즘에는 1개의 작업 비용이 듭니다.
• O(n*log(n)) 알고리즘에는 14개의 작업 비용이 듭니다.
• O(n2) 알고리즘은 1번의 작업 비용을 발생시킵니다.

나는 계산을 하지 않았지만 O(n2) 알고리즘을 사용하면 커피를 마실 시간이 있다고 말하고 싶습니다(심지어 두 잔!). 데이터 볼륨에 0을 하나 더 추가하면 낮잠을 잘 수 있는 시간이 생깁니다.

더 깊이 들어가자

귀하의 정보는 다음과 같습니다

• 좋은 해시 테이블 조회는 O(1)에서 요소를 찾습니다.
• 균형이 잘 잡힌 트리를 검색하면 O(log(n))의 결과가 생성됩니다.
• 배열을 검색하면 O(n)의 결과가 생성됩니다.
• 최고의 정렬 알고리즘의 복잡성은 O(n*log(n))입니다.
• 잘못된 정렬 알고리즘의 복잡성은 O(n2)입니다.

참고: 다음 부분에서는 이러한 알고리즘과 데이터 구조를 살펴보겠습니다.

알고리즘 시간 복잡도에는 여러 유형이 있습니다.

• 평균 사례 시나리오
• 최선의 시나리오
• 그리고 최악의 시나리오

시간 복잡성은 종종 최악의 시나리오입니다.

나는 알고리즘의 시간 복잡도에 대해서만 이야기했지만 복잡성은 다음에도 적용됩니다.

• 알고리즘의 메모리 소비
• 디스크 I/O 소비 알고리즘

물론 n2보다 더 심각한 문제가 있습니다. 예를 들면 다음과 같습니다.

• n4: 이건 정말 끔찍해요! 언급된 알고리즘 중 일부는 이러한 복잡성을 가지고 있습니다.
• 3n: 이건 더 심해요! 이 기사의 중간 부분에서 보게 될 알고리즘 중 하나는 이러한 복잡성을 가지고 있습니다(실제로 많은 데이터베이스에서 사용됩니다).
• 팩토리얼 n: 적은 양의 데이터로도 결과를 얻을 수 없습니다.
• nn: 이런 복잡성에 직면했다면, 이것이 정말로 당신의 활동 분야인지 자문해 보아야 합니다...

참고: 나는 빅 O 지정에 대한 실제 정의를 제공하지 않았으며 단지 아이디어만 제공했습니다. 이 기사는 다음에서 읽을 수 있습니다. 위키피디아 실제(점근적) 정의를 위해.

병합정렬

컬렉션을 정렬해야 할 때 어떻게 하시나요? 무엇? sort() 함수를 호출합니다... 좋아요, 좋은 답변입니다... 하지만 데이터베이스의 경우 이 sort() 함수가 작동하는 방식을 이해해야 합니다.

몇 가지 좋은 정렬 알고리즘이 있으므로 가장 중요한 것에 중점을 두겠습니다. 병합 정렬. 지금은 데이터 정렬이 왜 유용한지 이해하지 못할 수도 있지만 쿼리 최적화 부분 이후에 해야 합니다. 또한 병합 정렬을 이해하면 나중에 다음과 같은 일반적인 데이터베이스 조인 작업을 이해하는 데 도움이 됩니다. 병합 어울리다 (합병조합).

병합

많은 유용한 알고리즘과 마찬가지로 병합 정렬은 트릭을 사용합니다. N/2 크기의 정렬된 배열 2개를 N 요소 정렬 배열로 결합하는 데 드는 작업 비용은 N개뿐입니다. 이 작업을 병합이라고 합니다.

간단한 예를 통해 이것이 무엇을 의미하는지 살펴보겠습니다.

이 그림은 최종 정렬된 8개 요소 배열을 작성하려면 2개의 4개 요소 배열을 한 번만 반복하면 된다는 것을 보여줍니다. 4개 요소로 구성된 배열이 모두 이미 정렬되어 있으므로:

• 1) 두 배열의 두 현재 요소를 비교합니다 (처음에는 현재 = 첫 번째)
• 2) 그런 다음 가장 작은 것을 가져와 8 요소 배열에 넣습니다.
• 3) 가장 작은 요소를 가져온 배열의 다음 요소로 이동합니다.
• 배열 중 하나의 마지막 요소에 도달할 때까지 1,2,3을 반복합니다.
• 그런 다음 다른 배열의 나머지 요소를 가져와서 8개 요소 배열에 넣습니다.

이는 4개 요소 배열이 모두 정렬되어 있으므로 해당 배열에서 "뒤로 돌아갈" 필요가 없기 때문에 작동합니다.

이제 우리는 트릭을 이해했으므로 병합을 위한 의사 코드는 다음과 같습니다.

array mergeSort(array a)
   if(length(a)==1)
      return a[0];
   end if

   //recursive calls
   [left_array right_array] := split_into_2_equally_sized_arrays(a);
   array new_left_array := mergeSort(left_array);
   array new_right_array := mergeSort(right_array);

   //merging the 2 small ordered arrays into a big one
   array result := merge(new_left_array,new_right_array);
   return result;

병합 정렬은 문제를 더 작은 문제로 나눈 다음 더 작은 문제의 결과를 찾아 원래 문제의 결과를 얻습니다(참고: 이 유형의 알고리즘을 분할 정복이라고 합니다). 이 알고리즘을 이해하지 못하더라도 걱정하지 마세요. 처음 봤을 땐 이해가 안 됐어요. 도움이 될 수 있다면 이 알고리즘을 XNUMX단계 알고리즘으로 봅니다.

• 분할 단계(어레이가 더 작은 어레이로 분할됨)
• 정렬 단계에서는 작은 배열을 결합하여(union을 사용하여) 더 큰 배열을 형성합니다.

분할 단계

분할 단계에서는 배열이 3단계에 걸쳐 단일 배열로 분할됩니다. 공식적인 단계 수는 log(N)입니다(N=8, log(N) = 3이므로).

이것을 어떻게 알 수 있습니까?

나는 천재다! 한마디로 - 수학. 아이디어는 각 단계가 원래 배열의 크기를 2로 나누는 것입니다. 단계 수는 원래 배열을 두 개로 나눌 수 있는 횟수입니다. 이것이 로그(밑 2)의 정확한 정의입니다.

정렬 단계

정렬 단계에서는 단일(단일 요소) 배열로 시작합니다. 각 단계마다 여러 병합 작업을 적용하며 총 비용은 N = 8 작업입니다.

• 첫 번째 단계에는 각각 4개의 작업이 필요한 2개의 병합이 있습니다.
• 두 번째 단계에는 각각 2개의 작업이 필요한 4개의 병합이 있습니다.
• 세 번째 단계에서는 1개의 작업이 필요한 8개의 병합이 있습니다.

log(N) 단계가 있으므로, 총 비용 N * log(N) 작업.

병합 정렬의 장점

이 알고리즘이 왜 그렇게 강력한가요?

왜냐하면 :

• 새 배열을 생성하지 않고 입력 배열을 직접 수정할 수 있도록 이를 변경하여 메모리 사용 공간을 줄일 수 있습니다.

참고: 이러한 유형의 알고리즘을 in-장소 (추가 메모리 없이 정렬)

• 상당한 디스크 I/O 오버헤드를 발생시키지 않고 디스크 공간과 소량의 메모리를 동시에 사용하도록 변경할 수 있습니다. 현재 처리 중인 부분만 메모리에 로드하는 것이 아이디어입니다. 이는 100MB 메모리 버퍼만으로 수 기가바이트 크기의 테이블을 정렬해야 할 때 중요합니다.

참고: 이러한 유형의 알고리즘을 외부 정렬.

• 여러 프로세스/스레드/서버에서 실행되도록 변경할 수 있습니다.

예를 들어 분산 병합 정렬은 핵심 구성 요소 중 하나입니다. 하둡 (빅데이터의 구조)

• 이 알고리즘은 납을 금으로 바꿀 수 있습니다(정말입니다!).

이 정렬 알고리즘은 대부분의(전부는 아니지만) 데이터베이스에서 사용되지만 유일한 것은 아닙니다. 더 알고 싶다면 이 글을 읽어보세요 연구 작업, 일반적인 데이터베이스 정렬 알고리즘의 장단점을 논의합니다.

배열, 트리 및 해시 테이블

이제 시간복잡도와 정렬에 대한 개념을 이해했으니, 3가지 데이터 구조에 대해 알려드리겠습니다. 이것이 중요한 이유는 그들이 현대 데이터베이스의 기초. 컨셉도 소개할게요 데이터베이스 인덱스.

Массив

XNUMX차원 배열은 가장 간단한 데이터 구조입니다. 테이블은 배열로 생각될 수 있습니다. 예를 들어:

이 2차원 배열은 행과 열이 있는 테이블입니다.

• 각 줄은 엔터티를 나타냅니다.
• 열은 엔터티를 설명하는 속성을 저장합니다.
• 각 열은 특정 유형(정수, 문자열, 날짜...)의 데이터를 저장합니다.

이는 데이터를 저장하고 시각화하는 데 편리하지만 특정 값을 찾아야 하는 경우에는 적합하지 않습니다.

예를 들어, 영국에서 일하는 모든 남성을 찾으려면 각 행을 보고 해당 행이 영국에 속하는지 확인해야 합니다. N번의 거래 비용이 발생합니다.어디에서 N - 줄 수, 나쁘지 않은데 더 빠른 방법이 있을까요? 이제 우리가 나무에 대해 알아갈 시간입니다.

참고: 대부분의 최신 데이터베이스는 테이블을 효율적으로 저장하기 위해 힙 구성 테이블 및 인덱스 구성 테이블과 같은 확장 배열을 제공합니다. 그러나 이것이 열 그룹에서 특정 조건을 빠르게 찾는 문제를 바꾸지는 않습니다.

데이터베이스 트리 및 인덱스

이진 검색 트리는 특별한 속성을 가진 이진 트리입니다. 각 노드의 키는 다음과 같아야 합니다.

• 왼쪽 하위 트리에 저장된 모든 키보다 큼
• 오른쪽 하위 트리에 저장된 모든 키보다 작습니다.

이것이 시각적으로 무엇을 의미하는지 봅시다

생각

이 트리에는 N = 15개의 요소가 있습니다. 208을 찾고 있다고 가정해 보겠습니다.

• 키가 136인 루트에서 시작합니다. 136<208이므로 노드 136의 오른쪽 하위 트리를 봅니다.
• 398>208 따라서 노드 398의 왼쪽 하위 트리를 보고 있습니다.
• 250>208 따라서 노드 250의 왼쪽 하위 트리를 보고 있습니다.
• 200<208이므로 노드 200의 오른쪽 하위 트리를 보고 있습니다. 하지만 200에는 오른쪽 하위 트리가 없습니다. 값이 존재하지 않습니다 (존재한다면 오른쪽 하위 트리 200에 있을 것이기 때문입니다).

이제 내가 40을 찾고 있다고 가정해 보겠습니다.

• 키가 136인 루트에서 시작합니다. 136 > 40이므로 노드 136의 왼쪽 하위 트리를 봅니다.
• 80 > 40이므로 노드 80의 왼쪽 하위 트리를 보고 있습니다.
• 40= 40, 노드가 존재합니다. 노드 내부의 행 ID(그림에는 표시되지 않음)를 검색하고 테이블에서 지정된 행 ID를 찾습니다.
• 행 ID를 알면 데이터가 테이블의 어디에 있는지 정확히 알 수 있으므로 즉시 검색할 수 있습니다.

결국 두 검색 모두 트리 내부의 수준 수만큼 비용이 발생합니다. 병합 정렬 부분을 주의 깊게 읽어보면 log(N) 수준이 있다는 것을 알 수 있습니다. 그것은 밝혀, 검색 비용 로그(N), 나쁘지 않다!

우리의 문제로 돌아가자

그러나 이것은 매우 추상적이므로 문제로 돌아가 보겠습니다. 단순한 정수 대신 이전 표에 있는 누군가의 국가를 나타내는 문자열을 상상해 보세요. 테이블의 "국가" 필드(3열)를 포함하는 트리가 있다고 가정해 보겠습니다.

• 영국에서 일하는 사람이 누구인지 알고 싶다면
• 영국을 나타내는 노드를 얻기 위해 트리를 봅니다.
• "UKnode" 내에서 영국 근로자 기록의 위치를 ​​찾을 수 있습니다.

배열을 직접 사용하는 경우 이 검색에는 N 작업 대신 log(N) 작업이 소요됩니다. 방금 제시한 내용은 다음과 같습니다. 데이터베이스 인덱스.

키(예: 필드 그룹)를 비교하는 기능이 있는 한 모든 필드 그룹(문자열, 숫자, 2줄, 숫자 및 문자열, 날짜...)에 대한 인덱스 트리를 구축하여 설정할 수 있습니다. 열쇠 사이에서 순서를 정하세요 (이는 데이터베이스의 모든 기본 유형의 경우입니다).

B+트리인덱스

이 트리는 특정 값을 얻는 데는 효과적이지만, 필요한 경우에는 큰 문제가 있습니다. 두 값 사이에 여러 요소 가져오기. 트리의 각 노드를 살펴보고 이 두 값 사이에 있는지 확인해야 하기 때문에 O(N)의 비용이 듭니다(예: 트리 순회 순서를 사용하여). 게다가 이 작업은 전체 트리를 읽어야 하기 때문에 디스크 I/O 친화적이지 않습니다. 효율적으로 실행하는 방법을 찾아야 합니다. 범위 요청. 이 문제를 해결하기 위해 최신 데이터베이스는 B+Tree라는 이전 트리의 수정된 버전을 사용합니다. B+트리 트리에서:

• 가장 낮은 노드(잎)만 가게 정보 (관련 테이블의 행 위치)
• 나머지 노드는 여기에 있습니다 라우팅을 위해 올바른 노드로 검색 중.

보시다시피 여기에는 더 많은 노드가 있습니다(두 번). 실제로 올바른 노드(관련 테이블의 행 위치를 저장함)를 찾는 데 도움이 되는 추가 노드인 "결정 노드"가 있습니다. 그러나 검색 복잡도는 여전히 O(log(N))입니다(한 단계만 더 있음). 가장 큰 차이점은 하위 수준의 노드는 후속 노드에 연결됩니다..

이 B+Tree를 사용하여 40에서 100 사이의 값을 찾는 경우:

• 이전 트리에서 했던 것처럼 40(또는 40이 존재하지 않는 경우 40 이후 가장 가까운 값)을 찾으면 됩니다.
• 그런 다음 40명에 도달할 때까지 직접 상속인 링크를 사용하여 100명의 상속인을 수집하세요.

M개의 후속 항목을 찾았고 트리에 N개의 노드가 있다고 가정해 보겠습니다. 특정 노드를 찾는 데는 이전 트리와 마찬가지로 log(N) 비용이 듭니다. 하지만 일단 이 노드를 얻으면 M개의 작업에서 M개의 후속 노드를 참조하여 해당 후속 노드를 얻게 됩니다. 이 검색 비용은 M+log(N)입니다. 이전 트리의 N개 작업과 비교한 작업입니다. 또한 전체 트리(M+log(N) 노드만)를 읽을 필요가 없으므로 디스크 사용량이 줄어듭니다. M이 작고(예: 200행) N이 크다면(1행) 큰 차이가 발생합니다.

그러나 여기에는 (다시!) 새로운 문제가 있습니다. 데이터베이스(따라서 연관된 B+Tree 인덱스)에서 행을 추가하거나 삭제하는 경우:

• B+트리 내부의 노드 사이의 순서를 유지해야 합니다. 그렇지 않으면 정렬되지 않은 트리 내부의 노드를 찾을 수 없습니다.
• B+Tree에서 가능한 최소 수준 수를 유지해야 합니다. 그렇지 않으면 O(log(N)) 시간 복잡도는 O(N)이 됩니다.

즉, B+Tree는 자동 정렬되고 균형을 이루어야 합니다. 다행히 이는 스마트 삭제 및 삽입 작업을 통해 가능합니다. 그러나 이는 비용이 발생합니다. B+ 트리의 삽입 및 삭제 비용은 O(log(N))입니다. 그렇기 때문에 여러분 중 일부는 그런 말을 들었습니다. 너무 많은 인덱스를 사용하는 것은 좋은 생각이 아닙니다. 정말, 테이블에서 행의 빠른 삽입/업데이트/삭제 속도가 느려지고 있습니다.데이터베이스는 각 인덱스에 대해 비용이 많이 드는 O(log(N)) 작업을 사용하여 테이블의 인덱스를 업데이트해야 하기 때문입니다. 게다가 인덱스를 추가하면 작업 부하가 더 커집니다. 거래 관리자 (글 마지막 부분에 설명하겠습니다).

자세한 내용은 Wikipedia 기사를 참조하세요. B+나무. 데이터베이스에 B+Tree를 구현하는 예를 보려면 다음을 살펴보세요. 이 문서 и 이 문서 최고의 MySQL 개발자로부터. 둘 다 InnoDB(MySQL 엔진)가 인덱스를 처리하는 방법에 중점을 둡니다.

참고: 한 독자는 저수준 최적화로 인해 B+ 트리가 완전히 균형을 이루어야 한다고 말했습니다.

해시테이블

마지막으로 중요한 데이터 구조는 해시 테이블입니다. 이는 값을 빠르게 조회하려는 경우 매우 유용합니다. 더욱이 해시 테이블을 이해하면 나중에 해시 조인이라고 하는 일반적인 데이터베이스 조인 작업을 이해하는 데 도움이 됩니다. 해시 조인). 이 데이터 구조는 데이터베이스에서 일부 내부 항목(예: 잠금 테이블 또는 버퍼 풀, 나중에 이 두 개념을 모두 살펴보겠습니다.

해시 테이블은 키로 요소를 빠르게 찾는 데이터 구조입니다. 해시 테이블을 작성하려면 다음을 정의해야 합니다.

• ключ 당신의 요소에 대한
• 해시 함수 열쇠용. 계산된 키 해시는 요소의 위치를 ​​제공합니다( 세그먼트 ).
• 키 비교 기능. 올바른 세그먼트를 찾았으면 이 비교를 사용하여 세그먼트 내에서 찾고 있는 요소를 찾아야 합니다.

간단한 예

명확한 예를 들어보겠습니다.

이 해시 테이블에는 10개의 세그먼트가 있습니다. 제가 게을러서 5개 부분만 찍었는데, 당신이 똑똑하다는 걸 알기 때문에 나머지 5개 부분은 직접 그려보도록 하겠습니다. 나는 키의 모듈로 10 해시 함수를 사용했습니다. 즉, 해당 세그먼트를 찾기 위해 요소 키의 마지막 숫자만 저장합니다.

• 마지막 숫자가 0이면 요소는 세그먼트 0에 속합니다.
• 마지막 숫자가 1이면 요소는 세그먼트 1에 속합니다.
• 마지막 숫자가 2이면 요소는 영역 2에 속합니다.
• ...

내가 사용한 비교 함수는 단순히 두 정수 사이의 동일성입니다.

요소 78을 얻고 싶다고 가정해 보겠습니다.

• 해시 테이블은 78의 해시 코드인 8을 계산합니다.
• 해시 테이블은 세그먼트 8을 보고 첫 번째로 찾은 요소는 78입니다.
• 그녀는 항목 78을 당신에게 돌려줍니다.
• 검색 비용은 2개 작업뿐입니다. (하나는 해시 값을 계산하기 위한 것이고 다른 하나는 세그먼트 내의 요소를 조회하기 위한 것입니다).

이제 요소 59를 얻고 싶다고 가정해 보겠습니다.

• 해시 테이블은 59의 해시 코드인 9을 계산합니다.
• 해시 테이블은 세그먼트 9에서 검색하며 발견된 첫 번째 요소는 99입니다. 99!=59이므로 요소 99는 유효한 요소가 아닙니다.
• 동일한 논리를 사용하여 두 번째 요소(9), 세 번째 요소(79), ..., 마지막 요소(29)를 가져옵니다.
• 요소를 찾을 수 없습니다.
• 검색에는 7개의 작업이 소요됩니다..

좋은 해시 함수

보시다시피, 찾고 있는 가치에 따라 비용이 동일하지 않습니다!

이제 키의 해시 함수 모듈로 1을 변경하면(즉, 마지막 000자리 사용) 세그먼트 000에 요소가 없기 때문에 두 번째 조회에는 6번의 작업만 수행됩니다. 진짜 과제는 매우 적은 수의 요소를 포함하는 버킷을 생성할 좋은 해시 함수를 찾는 것입니다..

내 예에서는 좋은 해시 함수를 찾는 것이 쉽습니다. 그러나 이것은 간단한 예이며 키가 다음과 같을 때 좋은 해시 함수를 찾는 것이 더 어렵습니다.

• 문자열(예: 성)
• 2줄(예: 성 및 이름)
• 2줄 및 날짜(예: 성, 이름, 생년월일)
• ...

좋은 해시 함수를 사용하면 해시 테이블 조회 비용이 O(1).

배열과 해시 테이블

왜 배열을 사용하지 않습니까?

흠, 좋은 질문이네요.

• 해시 테이블은 다음과 같습니다. 메모리에 부분적으로 로드됨, 나머지 세그먼트는 디스크에 남아 있을 수 있습니다.
• 배열의 경우 메모리에서 연속적인 공간을 사용해야 합니다. 큰 테이블을 로드하는 경우 충분한 연속 공간을 찾는 것이 매우 어렵습니다..
• 해시 테이블의 경우 원하는 키(예: 국가 및 사람의 성)를 선택할 수 있습니다.

자세한 내용은 다음 기사를 참조하세요. 자바해시맵, 이는 해시 테이블을 효율적으로 구현한 것입니다. 이 기사에서 다루는 개념을 이해하기 위해 Java를 이해할 필요는 없습니다.

출처 : habr.com