[질문] db에서 값 찾을 때 왜 O(1)임?

[익명(223.39)]

O(N)이어야 하는거 아님?
이진탐색하더라도 O(logN)인데 O(1)이 어떻게 가능함???

[익명(183.96)]

해시테이블인가봐

[익명(106.101)]

디비 인덱스 일반적으로 b-tree라서 O(logn)일껀데

[익명(175.223)]

개소리를 할거면 제발 출처를 좀 가져와 빠가새끼야

[익명(115.91)]

옛날에 봤던거 같음. 뇌피셜임 ㅇㅇ

[익명(39.7)]

누가 그런얘기함?

[익명(115.91)]

옛날에 개발문서에서 봤던거 같아서... 기억 가물가물하긴 하지만 한번 물어본거

[9rum(msh01170)]

Learned index라도 보셨나 LSM 트리 기반의 DB에서 기계학습을 이용해서 memtable이 flush될 때 SSTable의 각 key에 대한 block index를 학습시키면 거의 100%에 가까운 정확도로 value를 상수 시간에 찾을 수 있음 근데 이건 on-disk 구조라서 memtable에서 찾는 시간 같은 건 전부 상수처리하기 때문에 big-O notation으로 표기하기는 좀 그럼

[9rum(msh01170)]

B+ 트리 기반의 색인 구조에도 적용되네요
자세한 건 아래 ALEX를 읽어보길 바람
https://arxiv.org/abs/1905.08898

[익명(115.91)]

우오..... 개멋있다 ㄷㄷㄷㄷ