전체 글33 [CMU 15-445 Intro to DB Sys] Lec07 Hash Tables DBMS에 사용되는 자료구조의 디자인에 있어서는 data organization(어떻게 효율적으로 access할 수 있을지), concurrency(여러 Thread가 문제 없이 access할 수 있도록)를 고려해야 함. Hash Tables unordered associative array that maps keys to values로서, 해쉬함수를 통해 key로부터 value가 담긴 곳의 offset을 계산한다. space complexity는 $O(n)$, time complexity는 평균적으로 $O(1)$, 최악의 경우 $O(n)$다. 그럼에도 불구하고 DBMS에서는 $O(1)$과 같은 constant도 최적화하는 것이 중요하다.Hash Function 해쉬함수는 large key space에서.. 2024. 1. 4. [UCB CS61C] Lec06 Floating Point floating point representation: 1.xxx * 2^yyyy의 형식으로 표현 IEEE754: 1 sign bit, 8 exponent bits, 23 significand bits sign bit가 1이면 음수, 0이면 양수 앞에 "1."이 생략되어있다고 보기 때문에, significand는 언제나 0에서 1 사이의 수가 된다. 모든 숫자가 0인 경우를 0으로 약속한다. exponent에는 biased notation(127)을 사용한다. unsigned value를 생각한 뒤에 127을 빼주면 된다. 따라서 $(-1)^{S} (1+\text{Significand}) 2^{\text{exponent}-127}$ Special Numbers 무한대는 exponent가 모두 1이고 si.. 2024. 1. 4. [CMU 15-445 Intro to DB Sys] Lec06 Memory & Disk IO spatial하게는 함께 사용되는 페이지들을 디스크에서 물리적으로 가깝게 유지하고 싶으며, temporal하게는 디스크에서 읽어올 때 발생하는 stall의 횟수를 최소화하는 것이다. Buffer Pool buffer pool은 디스크로부터 읽어온 페이지들을 보관하는 in-memory cache로서, 커다란 메모리 구역임. 이는 array of fixed-size pages로 구성되어 있음. 개별 entry를 Frame이라고 부름. DBMS에서 특정 페이지를 요청하게 되면 exact copy가 frame에 옮겨짐. dirty page는 buffer된 채로 있으며, 즉시 쓰여지지 않음. page table: 현재 메모리 상에 있는 페이지들의 현황을 관리함. 주로 fixed-size hash table이 사용.. 2024. 1. 4. [UCB CS162 OS] Lec03 Threads thread: single unique execution context Motivation thread는 여러 작업을 한번에(multiples things at once) 처리할 수 있도록 해준다. multiprocessing과 multiprogramming은 다르다. threads를 "concurrently" 실행시킨다는 것은? 스케줄러가 어떤 순서로든 interleaving하여 실행할 수 있는 것이다. -> 따라서 correctness에 대해 생각해야 한다. concurrency is not parallelism! concurrency는 여러 개를 한 번에 한다는 것이고, parellelism은 여러 개를 동시에(simultaneously) 한다는 것이다. thread를 만들어 주게 되면 마치 "또 .. 2024. 1. 4. [CS61C] Lec01 Intro 6 Great ideas in computer architecture abstraction(각 계층에서는 다른 계층에서 어떤 식으로 작동하는지를 이해할 필요 없이 사용 가능) Moore's Law principle of locality/memory hierarchy prallelism performance measurement & improvement dependability via redundancy(시스템이 fail하는 것을 방지) 오늘날 device의 수와 종류는 엄청나게 늘어나고 있음에 따라 아키텍처도 다양화 / 각 도메인에 맞는 시스템이 필요 과거에는 Moore's law와 dennard scaling 속에서 범용 컴퓨터가 지속 성장했기에 특화된 내지는 병렬컴퓨터를 개발하는 것이 무의미하였으나,.. 2024. 1. 1. [CMU 15-445 Intro to DB Sys] Lec05 Storage Models and DB Compression Workloads OLTP: write-heavy, simple OLAP: read-heavy, complex HTAP: OLAP와 OLTP가 함께 이루어지는 것으로 최근에 주목받고 있음 Storage models storage model은 tuple들이 어떻게 physically organize될지를 결정함. N-ary Storage Model(NSM) 소위 'row store'로서, 한 tuple에 대한 모든 attribute를 같은 페이지 상에 저장함. OLTP에 유리함(한 번의 fetch만으로 single tuple의 모든 attribute를 가져올 수 있음). 장점: update, insert, delete가 빠르고 OLTP에 좋음. 단점: table의 많은 부분을 scan하거나 .. 2024. 1. 1. 이전 1 2 3 4 5 6 다음