728x90 반응형 분류 전체보기319 [Database] 해싱 기법 (hashing techniques)과 충돌 해결 기법(collision resolution) 해싱(hashing): 해시키가 주어지면 해시 함수를 사용하여 디스크 블록의 주소를 표현한다. Internal hashing : 해시 테이블이 메인 메모리 주소를 찾아준다. 충돌(collision) 아무리 해시 함수를 잘 만든다고 해서 충돌 문제에서 자유로워질 수 있는 것은 아니다. 이러한 충돌을 피하기 위한 기법이 충돌 해결 기법이다.(collision resolution) 충돌 해결 기법은 대표적으로 3가지가 존재한다. 해싱 함수가 100으로 나눈 나머지 값이라고 가정한다. 1. 개방 주소법(open addressing) 충돌이 일어나게 되면 인접한 주소로 저장한다. 102와 202가 있다면 둘 다 해시 함수를 거친 결과가 2로 동일하다. 이런 경우 102는 2에 202는 3에 보관한다. 이후에 10.. 2022. 11. 25. [Database] Sequential Files(Ordered Files)의 정의와 트랜잭션 파일(transaction file) sequential files(ordered files)는디스크에 물리적으로 레코드들이 정렬되어 있다. 정렬된 파일은 이전 포스팅에서의 heap file같이 정렬되어있지 않은 파일에 비해 다음과 같은 장점을 가진다. 일반적으로 다음 레코드에 접근하기 위해서 블록에 새롭게 접근할 필요가 없다. (같은 블록에 있기 때문) key field가 정렬되어 있기 때문에 이진 탐색으로 빠르게 찾아낼 수 있다. 삽입 연산 이렇게 정렬되어있는 파일의 경우 삽입이 어렵다. 중간을 삽입하게 되면 그 뒤부터 전부 한 칸씩 밀리기 때문이다. 그래서 이를 해결하는 방법은 두 가지가 있다. 애초부터 블록에 삽입할 여분의 공간을 남겨둔다. 삽입의 경우 별도의 공간에 따로 진행하고 나중에 합친다. 삭제 연산 정렬된 파일에서 삭제 연산.. 2022. 11. 24. [Database] 더블 버퍼링 (double buffering) Program space : cpu가 사용 I/O space : 버퍼 관리자가 사용 디스크 속의 블록을 읽거나 쓰는 과정은 먼저 디스크에서 I/O space의 버퍼로 블록을 가져온다. 그리고 I/O space의 버퍼에 있는 것을 Program space로 가져와서 사용한다. 더블 버퍼링의 뜻은 버퍼가 두 개가 있다는 뜻이다. 더블 버퍼링을 사용할 경우 cpu가 I/O space의 한 버퍼를 사용중일 때 다른 버퍼는 디스크 안의 블록을 가져온다. 이런 식으로 교대로 동작하기 때문에 효율이 높아진다. pin-count : 현재 버퍼를 사용하고 있는 프로세서의 개수 dirty-bit : 비트의 업데이트 여부 버퍼 교체 전략 LRU(Least recently used) : 가장 최근에 잘 안 쓰인 것 MRU(M.. 2022. 11. 23. [Database] 디스크 안에 파일 레코드를 저장하는 방법 데이터는 파일 속에 레코드 형태로 보관이 된다. 이러한 레코드는 고정 길이 레코드 가변 길이 레코드 로 나뉜다. 고정 길이의 경우 길이가 고정되어 있기 때문에 원하는 정보를 얻기 쉬우나 가변 길이의 경우 구분자를 사용한다. 고정길이 가변길이 blocking factor (블록 당 레코드의 수) 블록의 크기가 512 Bytes이고 레코드의 크기가 100 Bytes라고 한다면 하나의 블록에는 5개의 레코드가 들어가고 12Bytes는 남게 된다. 즉 512/100에서 소수점을 버리면 이게 곧 blocking factor 이다. bfr(blocking factor) = B(블록 크기)/R(레코드 크기) 블록마다 남는 크기는 B - bfr * R 이다. 레코드들의 크기가 블록의 크기보다 커진다면 어떻게 할까? 두.. 2022. 11. 23. 이전 1 ··· 74 75 76 77 78 79 80 다음 728x90 반응형
