대규모 서비스 - O(log n) 알고리즘을 사용하는 이유

 

O(log n), O(n log n) 사용을 왜하는 걸까?

Google, Facebook의 경우 특정 테이블은 레코드가 몇십억, 몇백억 개가 있고, 테라 바이트, 페타 바이트 단위 이상이라고 합니다. 인덱스를 태우지 않고, 선형탐색으로 했을 때 레코드가 500만개만 있어도 요청 하나를 200초 안에도 처리하지 못합니다.

 

O(n) 알고리즘을 사용했을 때 1000만번 계산해야 할 때, O(log n) 알고리즘을 사용할 때 수십 번만 계산해도 처리가 가능합니다. 그 차이는 데이터가 커질수록 기하급수적으로 커지겠죠. 그래서 대규모 서비스를, 아니 중규모 이상 서비스를 고려한다면 O(n) 알고리즘을 O(log n) 알고리즘을 사용하는 것이 중요합니다.

 

이런 이유로, Basic하게 배운 선형 탐색들을 사용하기 보다는 코드상으로는 조금 더 복잡해보이지만, O(log n) 알고리즘을 사용하게 되는 것입니다.