Skip to content

태그: 자료구조

LSM 트리는 로그파일 기반으로 작성되는 방식의 파일 구조이다. LSM 트리는 Append-only 방법이어서 쓰기작업의 효울성이 좋다. 작동 방식 쓰기 작업 LSM 트리는 데이터를 disk에 바로 쓰지 않고, 정렬된 메모리 테이블(memTable)과 로그파일에 먼저 쓴다. 메모리 테이블은 주로 레드-블랙 트리를 사용하여 키-값 쌍을 기반으로 정렬된 구조를 유지한다. Memtable이 설정된 임계값에 도달하면, 그 내용은 디스크에 파일로 저장됩니다. 이때 데이터는 정렬된 상태로 저장되기 떄문에, 이 파일을 SSTable(Sorted String Table)이라고 부른다. SSTable은 불변성을 지니며, 한 번 기록된 후에는 변경되지 않는다. 이 구조는 데이터 일관성을 보장하며 압축이 진행되는 중에도

트라이는 문자열을 저장하고 효율적으로 검색하기 위한 트리 기반의 자료구조이다. 트라이는 루트 노드부터 시작하고, 각 노드는 문자를 나타낸다. 그리고 문자열은 루트에서 리프 노드까지의 경로로 표현된다. 트라이 자료구조를 사용하면 문자열을 매우 빠르게 검색할 수 있다. 특히 접두사 검색에 효율적이다. (O(m) 시간, m은 문자열 길이). 큰 메모리가 필요하다는 단점이 있다. 접두사를 바탕으로 한 자동 완성이나, 문자열 매칭을 위해 사용할 수 있다. 구현 트라이의 한 노드를 구성하는 객체는 자손 노드를 가리키는 포인터 목록과, 문자열의 끝인지를 나타내는 bool 변수로 구성된다. 자손 노드 포인터를 저장하기 위해 맵이나 벡터를 사용할 수 있다. struct Trie { map&x3C;char, Trie*>

세그먼트트리

세그먼트트리로 구간합을 구하는 알고리즘이다. --1:403F53"java.util.*; public class boj2042{ static Scanner sc = new Scanner(System.in); static long[] Tree; static long[] arr; static int log2(int x,int base){ return (int) Math.ceil(Math.log10(x)/Math.log10(2)); } /* makeTree : 길이가 8인 배열이 있을때 (1-8의 구간합)