최근에 저는 OEIS (Integer Sequence Online Encyclopedia)에 최근에 가지고 있던 특정 시퀀스를 찾으려고했습니다.데이터베이스 쿼리 시간은 데이터베이스 크기에 따라 어떻게 다릅니 까?
이제이 데이터베이스는 상당히 큽니다. 웹 사이트에 따르면 2006 년 (5 세) 판이 인쇄되면 750 권의 텍스트를 차지하게됩니다.
Google이 처리해야하는 것과 동일한 문제라고 확신합니다. 그러나로드 밸런싱을 이용하는 분산 시스템도 있습니다.
그러나 부하 분산을 무시하면 데이터베이스 크기에 비해 쿼리를 실행하는 데 시간이 얼마나 걸리나요?
또는 다른 말로하면 DB 크기와 관련하여 쿼리의 시간 복잡도는 얼마입니까?
편집 : 데이터베이스 엔진 구현 등을 포함한 요소, 인덱싱 전략의 수에 따라 달라집니다
1, 4, 9, 16, 25, 36, 49
쿼리, 데이터베이스 구조, 경합 등에 따라 크게 달라질 수 있습니다. 그러나 일반적으로 대부분의 데이터베이스는 인덱스를 사용할 수있는 방법을 찾을 것이며 인덱스는 일종의 트리 구조 (하나의 옵션에 대해 http://en.wikipedia.org/wiki/B-tree 참조)이거나 액세스 시간이 log (n)에 비례하거나 아니면 이 경우 액세스 시간은 평균 O (1)에 비례합니다 (작동 방식에 대한 설명은 http://en.wikipedia.org/wiki/Hash_function#Hash_tables 참조).
따라서 데이터 구조 유형에 따라 대답은 일반적으로 O (1) 또는 O (log (n))입니다.
이렇게하면 해시 함수를 사용하지 않는 이유가 궁금 할 수 있습니다. 여러 가지 이유가 있습니다. 해시 함수는 값 범위를 검색하기 어렵게 만듭니다. 해시 함수가 데이터를 잘 분배하지 못하면 액세스 시간이 O (n)이 될 수 있습니다. 해시는 가끔씩 크기가 조정되어야하므로 잠재적으로 매우 비쌉니다. 그리고 log (n)은 천천히 커지기 때문에 실용적인 모든 데이터 세트에서 상수에 가깝게 접근 할 수 있습니다. (1000에서 1 페타 바이트까지 5의 요소에 따라 다릅니다.) 그리고 종종 활발하게 요청 된 데이터는 나무가 RAM을 유지하는 더 나은 일을하는 일종의 지역성을 보여줍니다. 결과적으로 나무는 실제로 더 일반적으로 보입니다. (해시가 결코 드문 것은 아니지만)
: 일을 더 특정하게 입력 쿼리를 가정하려면 단순히 같은 숫자의 문자열을 찾고 있습니다 쿼리의 세부 사항, 사용 가능한 하드웨어, 데이터베이스 구성 등.
이러한 일반적인 질문에 대답 할 방법이 없습니다.
테라 바이트의 데이터를 가진 적절하게 설계되고 구현 된 데이터베이스는 잘못 설계된 작은 데이터베이스 (특히 인덱싱이없는 테이블과 잘못 처리되는 비 쿼리 및 상관 하위 쿼리 등)를 능가 할 수 있습니다. 대규모 데이터베이스가 필요할 때 대규모 디자인을 수행하기 위해 대용량 데이터를 사용할 것으로 예상되는 사람은 대규모 데이터베이스의 데이터베이스 디자인 전문가를 고용해야합니다. 또한 크기를 처리하는 데 필요한 장비 유형에 투자해야 할 수도 있습니다.
문자열의 길이는 얼마나됩니까? – Oded
Google은 OEIS보다 많은 ** 대규모 정보를 처리합니다. 그들이하는 방법은 [BigTable 논문] (http://labs.google.com/papers/bigtable.html)을 확인하십시오. –
@Oded : 문자열이 4 - 8 사이의 쉼표로 구분 된 정수라고 가정합니다. 각 정수는 1 - 10 자리입니다. –