테이블의 데이터 구조

Question

레코드를 나타내는 각 행이있는 테이블이 있고 여러 개의 열이있는 경우. 빠른 쿼리를 수행하고 열에 정렬하고 싶습니다. 어떤 데이터 구조를 사용할 수 있습니까?

저는 공간 효율적으로되고 싶습니다. 그렇지 않으면 쿼리 및 정렬을 위해 각 열에 정렬 된 결과를 캐시 할 수 있습니다. 그러나 테이블 자체 이외의 공간을 덜 소비하는 방법은 무엇입니까?

Answer 1

데이터의 복잡도에 따라 relational algebra의 구현을 찾고있을 수 있습니다. 즉, unordered set of tuples입니다.

일반적으로 구현은 어떤 형태로 B-tree입니다.

Answer 2

이것은 본질적으로 데이터베이스 프로그래밍 질문입니다. 칼럼마다 하나씩 인덱스가 필요할 것입니다 (이 답변의 나머지 부분은 우리가 단일 인덱스에 대해 말하고있는 것처럼 보이며, 필요하다면이 모든 것을 여러 번하는 것으로 상상해보십시오). 일반적인 솔루션은 해시 테이블과 검색 트리 (예 : B- 트리)를 포함하지만 물론 모든 열 항목을 포함하는 간단한 솔루션은 특히 공간 효율적이지 않습니다.

색인 : 블록으로 기록을 그룹화하고 색인의 각 블록에서 가장 낮은 검색 키가있는 레코드 만 저장하십시오. 병리학 적 상황이 아니라면 (아주 ​​낮은 값이 항상 추가됩니다), 이것은 당신에게 낮은 공간 요구 사항에서 훌륭한 성능을 줄 것입니다.

병리 적 상황을 다루기 위해 레코드를 블록으로 그룹화하는 다양한 방법을 살펴볼 수 있습니다. 검색 키의 관점에서 전체가 아닌 하위 집합을 찾을 수있을 때마다 전체 레코드 목록을 보관하지 않고 그룹으로 묶어 색인을 생성함으로써 .

(이 내가 그들의 프로그래머보다는 데이터베이스의 사용자 더 해요. 단지 생각이다. 나보다 더 많은 것을 알고 사람들이 실제로 수행 된 내용을보기 위해 몇 가지 조사를보십시오.)