🖥️SW Engineer/Distributed System

[ADV_db]Chap 4. Query-processing

# 질의 처리 순서 Parsing and Translation 들어온 질의문에서 문법적 오류가 없는지 확인하고, 관련 릴레이션들을 확인한다. DBMS내부에서 작동가능한 형태로 번역하고, relational algebra로 변환한다. View연산이 포함된 쿼리의 경우, View를 정의하는 모든 관계 대수 변환식으로 대체된다. Optimizer 여러 relational algebra 중에서 가장 좋은 Execution plan을 고른다. 고르는 기준은 데이터베이스에 파일이 저장된 방식이나 인덱스의 유무에 따라 달라지는 Cost를 기준으로 가장 낮은 Cost를 가진 Execution plan을 선택한다. Evaluation 연산 처리에 대한 주석이 달린 relational-algebra operation을 e..

[ADV_db]Chap 12-14. 연습문제

# Chap 12 . Physical storage system 12.1 SSD를 저장장치로 사용할 수도 있고, 아니면 저장장치와 메모리간의 버퍼로 사용할 수도 있다. 이 중 만약 real-time에 사용되는 SSD라면 어떤 용도로 쓰는게 적합할까?그리고 만약 엄청 큰 릴레이션이 있는데 이 중 일부만 자주 이용되는 경우라면 SSD를 어떻게 활용하는게 좋을지 설명하시오 Real-time의 경우 저장장치의 용도로 쓰는 게 더 성능을 보장할 수 있다. 큰 릴레이션의 경우에는 자주 이용하는 부분을 캐시나 버퍼의 형태로 SSD를 사용하는 것이 좋다. 12.2 어떤 데이터베이스는 디스크에서 안쪽 Track은 사용하지 않고 바깥쪽 Track만 사용하는데 이런 경우의 장점에 대해 설명하시오. 어차피 안쪽이나 바깥쪽이나..

[ADV_db]Chap 3. Hash index

# Static Hashing Hashing 대부분 메인 메모리 내에 인덱스를 만들기 위해 사용되지만, 파일의 레코드를 정리할 때도 사용된다. 인덱스를 만들 때는 버켓에 레코드들의 인덱스들이 들어있지만, 파일을 관리할 때는 실제 레코드가 들어간다. Hash Index는 해시 함수를 통과해서 나오는 값을 Search key값으로 사용하는 방식이다. Bucket이라는 디스크 블록에 같은 해시 값을 가지는 여러 엔트리가 저장되어 있다. 만약 Bucket의 Index가 고정되어 있다면 Static Hashing 그렇지 않다면, Dynamic Hashing이라고 한다. 다른 서치 키 값을 가지더라도 해시 함수를 통과했을 때 값이 같다면 같은 Bucket에 위치하기 때문에 어떤 엔트리를 검색하기 위해서는 해당 B..

[ADV_db]Chap 3. Indexing - B+Tree 추가내용들

# B+tree Extensions B+Tree File Organization 리프 노드에 포인터가 아닌 레코드 자체를 저장하는 방식 삽입/삭제/갱신이 일어나더라도 항상 Clustered된 상태를 유지하게 해준다. 레코드가 포인터보다 사이즈가 크기 때문에 리프 노드에 들어가는 레코드의 최대 수는 리프 노드가 아닌 노드들의 포인터 수보다 작을 수 밖에 없다. 따라서 공간 활용도가 중요한데 이를 위해서 가능한 많은 Siblings를 Split/Merge에 포함시키게 된다. 그 결과 m개의 sibling노드가 재분배에 참여한다면 각 노드마다 최소⌊(m-1)n/m⌋개의 엔트리를 가지게 된다. 하지만 이 경우 리프 노드에 있던 레코드가 노드 사이즈보다 커져서 Split을 해야한다면, 레코드를 이동 시키는 비용은..

[ADV_db]Chap 3. Indexing - B+tree 검색,삽입,삭제

# B+Tree 검색 루트 노드부터 검색하는 key값인 v보다 큰 key값이 나올 때까지 검색하다 같은 key값을 가지면, P(i+1)로 아니면 P(i)로 가서 리프 노드가 될 때까지 반복한다. 하나의 노드는 보통 하나의 디스크 블록 사이즈인 4kb로 한다. 따라서 보통 하나의 index당 크기는 40byte로 정하고 Fanout n은 100정도로 하는 게 보통이다. 그럼 key가 백만개 있다고 가정했을 때, log50(1,000,000) = 4 이므로 검색할 때마다 4개의 노드를 지난다. Composite key(복합키) 만약 key가 primary key가 아닌 경우, 유일성을 보장하기 어렵다. 이런 경우, (ai , Ap)식으로 복합키를 만들어 유일성을 보장할 수 있다. 하지만, 이러면 더 많은 I..

[ADV_db]Chap 3. Indexing - B+Tree 소개

# B+Tree B+Tree vs Sequential index B+Tree Sequential index 장점 1. 삽입,삭제 과정에서 알아서 재구성이 일어난다. 2. 성능 유지를 위한 전체 파일 재구성이 필요하지 않다. 1. 쉽다 ㅋ 단점 삽입,삭제 과정이 좀 더 오래 걸리고, 트리를 저장할 추가 공간이 필요하다. 1. Overflow Block때문에 파일이 커질수록 성능이 떨어진다 2. 주기적으로 재정비가 요구된다. B+Tree 특징 B+tree에서의 모든 데이터는 리프 노드에 들어있거나, 그 주소가 저장되어 있다. 따라서 리프 노드를 제외한 노드를 "인덱스 노드"라 부르고, 리프 노드를 "데이터 노드"라 부른다. 모든 리프 노드는 연결리스트로 연결되어 있고, 순서대로 정렬되어 있다. 그리고 모든 ..