해봤어?

B-Tree란?B-Tree는 기존 이진 탐색 트리에서 최악의 경우 시간 복잡도가 O(N)이 되는 문제를 해결하기 위해, 노드들이 한쪽으로 치우치지 않도록 균형을 유지하도록 설계된 트리이다. 그렇다면 데이터베이스 인덱스는 왜 B-tree를 선택 했을까? 배열을 사용하지 않는 이유데이터베이스에 수십억건의 대량의 데이터가 저장될 수 있는데, 이를 배열로 관리하면 메모리에 모든 데이터를 한 번에 올려야 하므로 비효율적이다.또한 삽입, 삭제시 최악의 경우 O(N)으로 비효율적이다. 연결 리스트를 사용하지 않는 이유연결 리스트의 경우 배열의 단점인 삽입, 삭제시 시간복잡도가 O(1)로 효율적이다.하지만 연결 리스트의 경우 조회시 최악의 경우 시간 복잡도가 O(N)으로 비효율적이다. 해시 테이블을 사용하지 않는 이유..

Skip List스킵리스트는 여러 레벨의 연결 리스트를 확률적으로 구성해 평균 O(log N)에 탐색·삽입·삭제를 지원하는 자료구조 장점스킵 리스트는 다중 레벨로 구성된 연결 리스트 구조를 가지므로, 일반 연결 리스트의 탐색·삽입·삭제가 O(N)인 것에 비해 평균 O(log N)에 수행된다.범위 탐색이 효율적이다. O(log N + M)B-트리와 달리, 스킵 리스트는 별도의 리밸런싱 과정 없이 노드 간 포인터만 조작하여 삽입과 삭제가 가능하다.단점각 노드가 여러 레벨의 포인터를 갖기 때문에 연결 리스트에 비해 메모리 사용량이 많다.확률적 구조 특성상 최악의 경우에는 일반 연결 리스트와 동일한 O(N)의 시간 복잡도를 가질 수 있다. Redis Sorted Set은 왜 Skip List를 선택 했을까? a..

스레드풀을 사용하면서 생긴 궁금증을 정리해보려 합니다.Thread는 Runnable 객체만 실행할 수 있는데, ExecutorService(스레드 풀)는 어떻게 Callable 객체도 실행할 수 있을까? public Future submit(Callable task) { if (task == null) throw new NullPointerException(); RunnableFuture ftask = newTaskFor(task); execute(ftask); return ftask;}protected RunnableFuture newTaskFor(Callable callable) { return new FutureTask(callable);}ExecutorService에..

최근 SKT 해킹 사건으로 인해 유심 보호 및 교체 신청이 급증하면서 Tworld 접속 시 대기열이 발생했다.이에 따라 Tworld의 대기열 시스템이 어떤 방식으로 구현되어 있는지 추측해보려고 한다. 흐름 1. 대기열 큐 생성2. SSE 연결3. 대기열 큐 상태 조회 대기열 큐 생성 https://care.tworld.co.kr/api/queue{ "ticketId": "535357ec-2a08-4164-b245-5cbcf3511015", "usersInQueue": 45396, "nextPolling": 10, "status": "IN_WAIT_QUEUE"}HTTP/1.1 200 OK...set-cookie: WEB_SESSION=974c2d4a-6a69-45cd-910c-2e23..