• index: additional structure. data를 건드리지 않고 query 성능만을 올리는 목적.
    • write 시 index update도 필요 - write 성능 저하
    • Hash index: key-value data
      • Bitcask: key와 해당하는 byte offset value에 대한 hash 사용
      • Bitcask와 Riak에 대해 아시는 분? ram → disk backup
    • secondary index: primary index와 달리 unique하지 않음. 특정 쿼리들의 성능 향상 도모
    • clustered index: index와 data를 물리적으로 가까이 배치해 성능 향상
      • MySQL의 primary key는 clustered index
    • multi-column index
      • concatenated index: 여러 column을 concat해 index로 사용
        • 여러 column을 한 번에 호출 가능.
        • 지리 데이터에 주로 사용
    • full text search
      • fuzzy index: 오타를 고려한 index. ML과 연계되는 경우도 많음.
        • edit distance: 허용하는 오타 갯수
      • Lucene: SSTable과 비슷한 형태로 in-memory index를 통해 오타 보완
        • Levenshtein automation?이라는 word search 알고리즘에 적용 가능
    • in-memory: disk 저장을 위한 parsing 과정이 없어 성능 향상
      • 경우에 따라 disk에 anti-caching을 통해 공간 확보
  • log-structured
    • 용어
      • log: append-only 형태의 데이터
      • compaction: 중복 키 제거 및 재정렬. file segment들의 merging 포함될 수 있음
        • 고려 사항: File format, Deleting records, Crash recovery, Partial records, Concurrency
      • tombstone: special deletion record. merge 완료 후 이전 값들을 삭제하도록 함
    • 특징
      • write 속도 빠름
      • write 횟수가 적어 ssd에 적합
      • concurrency, crash recovery 용이
      • hash table을 memory에 올리므로 size 제한 엄격
      • 각 key를 individual하게 사용하므로 range query 부적합
    • SSTables: compaction 후 sort 과정을 거친 table. Sorted String Tables
      • meltable 구성 후 size가 threshold를 넘을 경우 disk에 sstable 형태로 이관
    • LSM-tree
      • LevelDB와 RocksDB, Cassandra와 HBase, Bigtable paper, Lucene과 Elasticsearch와 Solar
        • levelDB: leveled compaction. key range를 smaller SSTable로 나눔. disk space를 적게 사용
        • rocksDB: size-tiered. new, small SSTable이 old, large SSTable로 merge
      • SSTables와 같은 원리로 작동하는 storage engine
      • DB에 없는 key를 검색할 경우 느림: bloom filter 활용
  • page-structured
    • B-tree
      • 특정 size segment로 나눠 n단계 reference 적용
        • segment default size 4kb
      • 최초의 segment를 root라 하며 read의 시작 지점.
      • branching factor: 한 segment에 기록된 ref 갯수
      • key가 들어갈 공간이 부족한 경우 기존 segment가 half-full segment 2개로 분화
        • 중간에 crash 날 경우 orphan 생성 위험
      • segment size 4kb, branching factor 500: 256TB
      • 기본적으로 모든 key-value는 overwrite.
        • SSD는 block 단위로 delete, write 진행해야 함
      • concurrency에 불리
        • latches: lightweight locks
      • WAL: write-ahead log. aka redo log.
        • B-tree modification에 관한 append-only file
    • R-tree?: spatial index. two-dimentsional data를 single number로 번역
  • Data warehouse: 여러 db로부터 readonly로 데이터를 수집. analysis 용도로 사용
    • OLTP: transaction processing. 비교적 간단한 process가 빈번히 수행
    • OLAP: analytic process: 분석 등 복잡한 process 수행
      • bandwidth가 최대 bottleneck 중 하나
    • OLTP, OLAP를 위한 db를 분리하는 것이 효율적.
      • 서로 다른 query가 사용되나 user interface는 통일하기도 함.
    • Star schema: fact-table을 중심으로 여러 dim table이 연결된 구조
      • fact-table은 event 당 item이 생성되며 그 크기가 굉장히 클 수 있음
      • snowflake schema: dim-table을 일부 분리해 정규화한 형태. 복잡도 올라감
    • Column-Oriented Storage
      • column 단위로 file을 분리해 각각 저장하는 형태
      • 각 fille에 저장된 data의 순서가 critical
      • read 시 전체 row를 확인하지 않아 검색 속도 빠름
        • bandwidth도 효율적으로 사용
      • bitmap compression
        • duplicate key가 있을 경우 이를 bitmap으로 표현
        • or 연산을 통해 WHERE~IN 절 빠르게 처리 가능
        • duplicate key가 모여있을수록 효율적 저장 가능
          • sorting에 대한 충분한 고려 필요
      • write에 불리
        • 값 하나를 추가하려면 모든 파일에 접근 필요
    • Materialized views
      • 자주 사용되는 aggregation pattern의 결과값들을 미리 연산