홍카나의 공부방

해싱 방법 해시 함수를 이용해서 키 값 input에 대한 목표 레코드의 주소로 한 번에 찾아가는 방법이다. 직접 탐색에는 힙이나 B+tree에 비해서 훨씬 빠를 것이다. 여러 해싱 방법 중에서 버킷 해싱이라는 방법이 있다. 여기서 버킷은 하나의 주소를 가지면서 하나 이상의 레코드를 저장할 수 있는 파일의 한 구역을 지칭한다. 각 버킷은 연결 리스트와 같은 자료 구조로 구현된다. 버킷 해싱은 키를 넣으면 해시 함수를 거쳐서 버킷 주소를 알려주는 구조다. 만약 해시 함수가 출력 값을 고르게 분포하지 않을 경우, 서로 다른 데이터가 같은 버킷에 할당되는 충돌 현상이 발생한다. 해시 충돌은 어쩔 수 없이 벌어지는 현상이다. 해시 함수의 출력 값이 무한하지 않기 때문이다. 이러면 특정 버킷이 오버플로우 될 수 있..

B+ 트리 MySQL은 B+트리로 인덱스가 구현되어 있다. B+ 트리는 인덱스 세트와 순차 세트라는 2가지 세트를 만든다. 인덱스 세트는 내부 노드로, 리프에 있는 키들에 대한 경로만 제공한다. 모든 키 값은 순차 세트(리프 노드)에 있다. 인덱스 세트는 직접 탐색을 지원하며, 순차 세트는 순차 탐색을 지원한다. B+ 트리는 B트리와 다르게 Best도 없고 Worst도 없다. 탐색은 무조건 O(log N)이다. B+ 트리의 루트 및 내부 노드 구조에는 레코드에 대한 포인터 값이 제외되어 있다. 반대로 리프 노드는 루트 및 내부 노드와 다르게 서브트리에 대한 포인터가 없다. 대신 레코드에 대한 포인터 값이 있고, 다음 리프노드에 대한 포인터가 존재한다. 순차 세트의 모든 리프 노드는 링크드 리스트 형태로 ..

임시 저장해 둔 글이 3번이나 날라갔다...... 의도치 않게 이 내용을 3번 이상 작성했다. 저장 잘하자. 데이터베이스의 저장 구조 데이터베이스 데이터의 용도에 맞게 적절하게 디스크에 저장할 필요가 있다. 그래서 가장 효율적인 저장구조를 선택하는 과정을 살펴본다. 이 과정은 DB의 쿼리 및 트랜잭션을 분석하여 데이터에 대한 접근 방식과 빈도를 고려하는 DB의 물리적 설계와 같다. 물리적 저장 장치에 데이터를 배치하고 접근하는 방법을 파일의 조직 방법이라고 한다. 파일 조직의 유형에는 순차 방법, 인덱스 방법, 해시 방법이 있는데 전부 살펴본다. 순차 방법 순차 방법의 대표적인 파일 유형으로는 힙 파일(heap file)이 있다. 레코드들이 삽입된 순서대로 파일에 저장된다. 힙 파일은 쉽다. 새로운 레코..

IAM IAM은 AWS 리소스에 대한 접근을 안전하게 제어할 수 있게 만들어주는 서비스다. 최초 AWS 계정 생성시 루트 사용자 권한을 받아서 사용하게 되지만, 이후에는 IAM 권한을 따로 부여하여 사용하는 것을 권장한다. IAM 정책을 설정하여 어떤 리소스에 접근할 수 있는지 여부를 사용자, 사용자 그룹 별로 지정할 수 있다. 이런 플로우로 도식화할 수 있다. S3 S3는 객체 스토리지 서비스로, 쉽게 말하면 웹에서 사용할 수 있는 하드 디스크다. 그리고 S3를 사용하여 정적 웹 사이트를 호스팅 할 수 있다. ( .html 파일을 올리고 정적 웹 사이트 호스팅을 활성화하면 된다. ) 이때 버킷의 정책 및 퍼블릭 엑세스 설정을 바꿔서 접근할 수 있도록 열어둬야 한다. CI / CD AWS에서는 SW 개발..