[책]소프트웨어 작동법 - 검색

원하는 데이터를 찾아내는 기술 - 검색

데이터를 모아둔 것 - 데이터 집합(data collection)
각 집합에 있는 개별 데이터 - 레코드(record)
하나의 레코드는 key에 의해 구분됨

검색

순차검색 - 순서없이 정렬되어 있음, 처음부터 모두 검색
소트(sort) - 데이터 집합을 특정 순서대로 정렬하는 것

선택소트 (selection sort)
1. 가장 작은 값 가져옴
2. 그다음 가장 작은 값 가져옴

퀵소트(quick sort)
* 피봇(pivot) : 목록 중 특정숫자
- 계산량과 처리속도를 줄인것
- 목록중 아무거나 하나 집고 그것을 기준으로 높은것과 낮은거 정렬
[2,10,1,3,7] ->(피봇:3) ->[ 2,1,3,10,7]->
3 을 기준으로 서브목록 1(2,1) 서브목록2(10,7) 생김
->서브목록1 피봇1->[[1,2],3,10,7]-> 서브목록2 피봇10 ->[[1,2],3,[7,10]]-> 정렬 완료

@ 피봇이 이렇게 가운데면 참 좋은데 한쪽으로 쏠리면 과도하게 많이 걸릴수도 있음
@ 일반적으로 레코드 수가 커질수록 퀵소트가 선택소트보다 성능이 좋음

이진검색 (binary search)
여기서 이진이란 (binary)를 뜻하는 것이 아니고 두개중 하나를 뜻한다.
* 찾고자 하는 데이터 48이라는 키를 갖고 있음
* 집합은 정렬되어 있다 가정함
1. 가운데 있는 레코드를 본다 (62) 9개 남음 [1,,,,62]
2. 가운데 있는 레코드를 본다 (23) 5개 남음 [23,,,62]
3. 가운데 있는 레코드를 본다 (47) 3개 남음 [47,48,62]
4. 가운데 있는 레코드를 본다 (48) 이때 48이 아닐경우 값이 없다 리턴

인덱싱
레코드는 실제 어딘가에 존재(메모리 혹은 하드디스크)

고정길이(fixed-size)방식
- 저장공간 낭비가 발생됨
- 성능상(검색 속도) 이득
-> 고정주소일 경우 특정 레코드의 주소를 찾기 쉽다
(길이가 20이고 주소가 1000부터 시작한다 하면 1000->1020->1040의 형태로 찾을수 있다)

가변길이(variable-size)방식
- 데이터의 길이에 맞춰 저장하는 방식
-> 검색할 경우 고정길이가 아니면 모든 레코드를 세는 수 밖에 없음

* 윈도우의 32, 64는 메인메모리 주소크기 (고정길이)

ex> 4개의 음악이 있다고 치면 실제 데이터 파일은 하드디스크에 저장 하고
한개의 제목과 실제 데이터 파일의 주소 값을 가진 키값을 고정길이 형태로 메모리에 저장


인덱스는 레코드 키와 주소로 구성된 테이블(목록)

슬롯(slot)
- 레코드 저장 위치

해싱
해시함수(hash function)를 통해 slot / 노래제목 / 데이터주소 형태로 저장
- 장점: 일일이 검색하지 않아도 해시 함수를 통해 한번에 접근 할 수 있음
- 단점 :  해시 키값이 중복, 즉 충돌이 발생
충돌 발생 시..
1. 다음슬롯에 채움
-> 그럼 해시 검색시 찾는것이 없으면 다음거부터 순차검색.. 다음 자리가 비어있으면
먼 슬롯까지 순차 검색을 하게 될것이고 굉장한 비효율 발생
2. 슬롯을 삭제 할경우 다음 슬롯에 저장된 것은 찾을수 없음
-> 해당 슬롯에 데이터 주소와 슬롯을 제외한 값은 비워둠(묘석)
==> 이러한 이유로 정기적으로 재해시를 해야됨, 그리고 중복이 발생하지 않도록 해시 알고리즘 중요

웹검색
- 구글의 인덱스 크기는 100페타바이트 == 1억기가 바이트

검색엔진은 로봇(robot)이라는 것을 사용한다.
- 사람의 간섭 없이 자동으로 인덱스를 만들어내는 프로그램

순위결과
- 인바운드 링크 : 외부홈페이지에서 내 홈페이지 페이지로 링크들.
이 인바운드 링크를 통해 순위를 매김

링크파밍(link farming)
- 이러한 인바운드 링크를 무료 호스트나 버려진 웹 사이트에 특정사이트 링크를 걸어인바운드 링크수를 고의적으로 늘리는 작업