파일구조II

HakJun·2022년 11월 7일
Database
1

Database

목록 보기
14/16
  1. Hashing Techniques
    • 키값이 주어졌을 때 해쉬함수를 통해 디스크 주소가 주어진다.
    • 해시를 쓰는 파일을 해쉬파일, 직접파일이라고 한다.
    • primary가 붙으면 그 방법에 따라 레코드가 저장되어 있음을 의미한다.
    • 해시 혹은 랜덤함수라고 한다.
    • 메모리에 가져와서 검색하는것은 메인 메모리에서 진행된다.
  2. Internal Hashing
    • ex) h(k) = K mod M
  3. 충돌문제
    • 키값에서 항상 서로다른 주소가 나온다는 보장이 없다.
    • 해쉬가 갖는 경우의 수가 실제 디스크 공간보다 훨씬 크기 때문이다. 1대1 매핑 자체가 불가능하다.
    • 충돌 해결 기법
      - Open addressing: 개방주소법
      • Chaining
      • 다중 해싱 방법
    • 개방주소법 : 들어갈 수 없다면 인접한 주소에 값을 할당하는 것, 빈공간이 나올때까지 주소값을 찾아야한다.
    • Chaining : 들어가야할 내용을 연결리스트로 묶어논 방법, 데이터 공간과 오버플로우 공간이 분리되어 있다.
    • 다중 해싱 방법 : 새로운 해시 함수를 사용하여 저장방법을 변경하는 것
  4. 좋은 해시 함수
    • 전체기억공간의 70~90%를 사용하는것을 가장 효율적이라고 한다.
    • 기억공간의 낭비를 줄이고, 충돌도 줄이는 방법이 효율적이다.
  5. 디스크파일을 위한 외부 해시
  6. 외부해시의 연산
    • 레코드를 찾고 없으면 오버플로우 체인을 따라가면 된다.
    • 삭제의 경우는 오버플로우의 공간의 레코드를 내부로 가져온다.
    • 연결리스트의 삭제 과정을 진행하여 체인을 유지시킨다.
  7. 정적 해시
    • 처음부터 정해진수의 버킷을 할당을 해놓은 경우 해시
    • 너무작게잡으면 충돌, 너무크게잡으면 공간낭비가 생기기때문에 재구성이 필요하게 된다.
  8. 동적파일 확장이 가능한 해시
    • Extendible hashing
      - 키값을 이진수로 표현한다
      • 해시를 통해 디렉토리 주소를 찾고 2차적으로 버킷 주소를 찾는다.
      • 실제 레코드들의 수가 적으면 두 디렉토리가 가리키는 곳을 하나의 파일 버킷으로 통일한다.
      • 키값
    • Linear hashing
      - h(k) = K mod M이였다면
      • 오버플로우 시 h1(k) = K mod 2M을 적용하여 블록을 나눈다..
    • Dynamic hashing
      - 디렉토리를 트리형태로 유지함
  9. RAID
    • level은 0~6까지 존재한다.
    • 비트레벨, 블록레벨로 나눠서 디스크에 저장하는 방법이 존재한다.
    • MTBF : 고장나지 않고 사용할 수 있는 시간, 디스크의 신뢰성을 의미
    • 100개의 디스크 드라이버를 쓰면 고장날 확률이 100배가 늘어난다.
    • 해결법은 rebundancy 데이터를 사용하는것이다.
    • 이로인해 추가적인 I/O, 관리비용이 발생하여 RAID를 사용한다.
    • Mirroring or Shadowing : 똑같은것을 두개를 두는 것, 동시에 두개가 고장이 나지 않으면 문제가 없다.
    • 여분의 정보를 저장하는것 -> parity bits, error-correcting codes -> MTTL이 매우 늘어난다.
  10. RAID의 성능적인 장점
    • data striping -> 비트,블록레벨 존재
    • 한쪽의 디스크에서 한 바이트씩 나눠서 읽어서 합치면 매우 큰 성능의 증가가 존재한다. 속도는 높은 반면 신뢰성의 측면에서 장점이 없다. 한쪽에서 고장나면 모든곳에 문제가 발생함
  11. RAID 조직과 레벨
    • 신뢰성과 효율성은 유사 반비례관계
      -RAID 0
      - Striping만 존재
      -RAID 1
      - 하나가 완전히 망가져도 하나는 완전하다, 속도측면에서는 효율성이 없다.
    • RAID 2: 한바이트의 비트를 흩어놓고, 3개의 디스크는 HAMMING CODE를 위한 공간이다.
    • RAID3 : 특정 디스크가 고장나면 1비트만으로 복구가 가능하다. BYTE단위 STRIPING
    • RAID4 : 블록 레벨 STRIPING
    • RAID5 : PARITY를 분산시켜 놓았다. 부하를 감소시킬 수 있다.
    • RAID6 : P+Q rebundancy, 두개의 디스크가 고장나도 두개까지 복구할 수 있다.
    • Hybrid RAID LEVELS : RAID 0+3 , RAID 1+0,..
profile
HakJun
백엔드 & 전공 공부
이전 포스트

파일 구조I

다음 포스트

인덱스 구조

0개의 댓글