본문 바로가기
PHP

[PHP] 바이너리 서치로 인덱스 필드값 찾기

by LightBlogger 2018. 5. 15.

다음과 같이 id, date_time의 필드를 가진 테이블이 있다 하자.



(예시의 자료 개수는 1000개이며, 직접 입력하고 싶다면 date_time.txt파일을 참고)



인덱스(index)는 id 필드에만 적용되어 있고, date_time 필드에는 없는 상황.


만일 테이블의 크기가 매우 클 경우, 쿼리에 조건을 다음과 같이 date_time 으로 걸면 질의시간이 상당히 오래 걸리게 된다.


SELECT * FROM date_table WHERE date_time>='2018-01-15' and date_time<'2018-02-15';


특정 date_time에 해당하는 id 를 찾을 수 있다면 다음과 같이 바꾸어 질의할 수 있다.


SELECT * FROM date_table WHERE id>='229' and id<'793';


id 에는 인덱스가 있으므로 시간이 매우 단축될 것이다.


인덱스가 없는 필드의 값으로 인덱스가 있는 필드의 값을 알아내는 코드를 작성해 보자.



일단 PHP틀을 만들고


<?php
$conn = mysqli_connect("localhost", "root", "123456789");
mysqli_select_db($conn, "test");
 ?>

<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <title></title>
  </head>
  <body>

<?php

?>
  </body>
</html>


해당 테이블의 가장 큰 id 를 변수로 저장하자.


우리는 바이너리 서치 Binary Search 라는 전략을 사용할 것인데,


쉽게 말하면 주어진 자료를 계속 반으로 나누며 원하는 값을 찾는 방법이다.


(이미지 출처: wikipedia)



가장 큰 id 값의 절반에서 시작해야 하므로, 일단 다음과 같이 가장 큰 id 값을 $max 에 저장한다.


$query = 'SELECT max(id) FROM date_table';

$result = mysqli_query($conn, $query);

$row = mysqli_fetch_row($result);

$max = $row[0];


<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <title></title>
  </head>
  <body>

<?php

$query = 'SELECT max(id) FROM date_table';
$result = mysqli_query($conn, $query);
$row = mysqli_fetch_row($result);
$max = $row[0];

?>
  </body>
</html>


이어서 우리가 찾고자 하는 날짜도 $date 에 설정해 놓고, 최소값 $min 도 1로 놓자.


$min = 1;

$date = '2018-01-15';


<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <title></title>
  </head>
  <body>

<?php

$query = 'SELECT max(id) FROM date_table';
$result = mysqli_query($conn, $query);
$row = mysqli_fetch_row($result);
$max = $row[0];
$min = 1;
$date = '2018-01-15';

?>
  </body>
</html>


이제 프로세스는 다음과 같다.



일단 최소값과 최대값의 평균으로 ID를 추측한다.


만일 추측한 아이디에 해당하는 날짜가, 우리가 설정해 놓은 $date 보다 크다면


$date에 해당하는 아이디는 왼쪽 절반에 있을 것이다.


이제 이전에 추측한 ID를 최대값(Max)으로 세팅하고, 다시 최소값과 최대값의 평균으로 ID를 추측한다.



만일 추측한 아이디에 해당하는 날짜가, 우리가 설정해 놓은 $date 보다 작다면


$date에 해당하는 아이디는, 이번에는 오른쪽에 있을 것이다.


이전에 추측한 ID는 최소값(Min)이 되고, 새롭게 ID를 추측한다.



이와 같은 과정을 반복하면 되겠다. 



일단 $id 를 최소값과 최대값의 평균으로 설정한다.


$id = round(($min+$max)/2);


id 는 정수여야하므로 결과를 round()에 넣어 반올림해 주었다.


이제 $id 로 쿼리를 돌려 나온 날짜를 파악한다.


  $query = sprintf("SELECT id, date_time FROM date_table where id=%d", $id);

  $result = mysqli_query($conn, $query);

  $row = mysqli_fetch_row($result);

  $row[1] = substr($row[1], 0, 10);


date_time 필드에서 시간은 필요 없으므로, substr() 을 이용해 왼쪽부터 10글자까지 잘라주었다.


만일 이렇게 나온 날짜가 $date보다 크다면 $id 는 $max가 되고, 새로운 $id는 $min과 $max의 평균으로 정의된다.


if($row[1]>$date){

  $max = $id;

  $id = round(($min+$max)/2);

}


만일 $row[1] 이 $date보다 작다면 $id 는 $min이 되고, 새로운 $id는 $min과 $max의 평균으로 정의된다.


else if($row[1]<$date){

  $min = $id;

  $id = round(($min+$max)/2);

}


여기까지 코드를 보면 다음과 같다.


<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <title></title>
  </head>
  <body>

<?php

$query = 'SELECT max(id) FROM date_table';
$result = mysqli_query($conn, $query);
$row = mysqli_fetch_row($result);
$max = $row[0];
$min = 1;
$date = '2018-01-15';

$id = round(($min+$max)/2);

  $query = sprintf("SELECT id, date_time FROM date_table where id=%d", $id);
  $result = mysqli_query($conn, $query);
  $row = mysqli_fetch_row($result);
  $row[1] = substr($row[1], 0, 10);
if($row[1]>$date){
  $max = $id;
  $id = round(($min+$max)/2);
} else if($row[1]<$date){
  $min = $id;
  $id = round(($min+$max)/2);
}

?>
  </body>
</html>


이제 날짜를 구하고 (크면/작으면)을 판단하는 부분을 반복문 안에 넣어 원하는 결과를 얻을 때까지 반복해야 한다.


$row[1]이 $date보다 크지도 작지도 않으면 반복을 멈추도록 하면 되겠다.


$end라는 변수를 생성해 다음과 같이 while()문을 만든다.


<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <title></title>
  </head>
  <body>

<?php

$query = 'SELECT max(id) FROM date_table';
$result = mysqli_query($conn, $query);
$row = mysqli_fetch_row($result);
$max = $row[0];
$min = 1;
$date = '2018-01-15';

$id = round(($min+$max)/2);

$end = 0;
while($end == 0){
  $query = sprintf("SELECT id, date_time FROM date_table where id=%d", $id);
  $result = mysqli_query($conn, $query);
  $row = mysqli_fetch_row($result);
  $row[1] = substr($row[1], 0, 10);
if($row[1]>$date){
  $max = $id;
  $id = round(($min+$max)/2);
} else if($row[1]<$date){
  $min = $id;
  $id = round(($min+$max)/2);
} else {
  $end = 1;
}

}

?>
  </body>
</html>



$end = 0;


으로 설정해 놓고


while($end == 0){


으로 반복문을 돌린다.


원하는 조건이 만족될 경우


else {

  $end = 1;

}


으로 탈출하게 될 것이다.



이것만으로는 결과가 나오지 않으므로 while 문 바깥에 echo로 결과를 출력한다.


echo $id;


<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <title></title>
  </head>
  <body>

<?php

$query = 'SELECT max(id) FROM date_table';
$result = mysqli_query($conn, $query);
$row = mysqli_fetch_row($result);
$max = $row[0];
$min = 1;
$date = '2018-01-15';

$id = round(($min+$max)/2);

$end = 0;
while($end == 0){
  $query = sprintf("SELECT id, date_time FROM date_table where id=%d", $id);
  $result = mysqli_query($conn, $query);
  $row = mysqli_fetch_row($result);
  $row[1] = substr($row[1], 0, 10);
if($row[1]>$date){
  $max = $id;
  $id = round(($min+$max)/2);
} else if($row[1]<$date){
  $min = $id;
  $id = round(($min+$max)/2);
} else {
  $end = 1;
}

}

echo $id;

?>
  </body>
</html>


완성이다. 실행시켜보자.



결과가 나오고 있다. id 251번에 해당하는 날짜는 2018-01-15일 것이다.


좋지만, 우리는 2018-01-15에 해당하는 첫 번째 아이디를 찾고 싶으므로


다시 Binary Search를 한번 더 돌려야 한다.


아까와 완전히 동일한 구조에, 다음 부분만 달라지면 되겠다.


$id 에 해당하는 날짜가 $date 와 같을 경우 해당 값을 $max로 설정


$id 에 해당하는 날짜가 $date 와 다를 경우 해당 값을 $min으로 설정


그러면 Binary Search 는 날짜가 달라지는 경계 지점까지 수렴해 들어갈 것이다.


코드는 다음과 같다.


$end = 0;

while($end == 0){

  $query = sprintf("SELECT id, date_time FROM date_table where id=%d", $id);

  $result = mysqli_query($conn, $query);

  $row = mysqli_fetch_row($result);

  $row[1] = substr($row[1], 0, 10);

if($row[1]==$date){

  $max = $id;

  $id = round(($min+$max)/2);

} else {

  $min = $id;

  $id = round(($min+$max)/2);

}


if($max==$min+1){

  $end = 1;

}


}


앞선 반복문과 동일한 구조다. 언급한대로 (크면/작으면) 대신 (같으면/다르면)을 판단하도록 하고,


수렴한 결과 $max 가 $min 과 1 차이 나면 반복문을 종료하도록 한다.



여기까지 코드를 다시 실행시켜보자.


<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <title></title>
  </head>
  <body>

<?php

$query = 'SELECT max(id) FROM date_table';
$result = mysqli_query($conn, $query);
$row = mysqli_fetch_row($result);
$max = $row[0];
$min = 1;
$date = '2018-01-15';

$id = round(($min+$max)/2);

$end = 0;
while($end == 0){
  $query = sprintf("SELECT id, date_time FROM date_table where id=%d", $id);
  $result = mysqli_query($conn, $query);
  $row = mysqli_fetch_row($result);
  $row[1] = substr($row[1], 0, 10);
if($row[1]>$date){
  $max = $id;
  $id = round(($min+$max)/2);
} else if($row[1]<$date){
  $min = $id;
  $id = round(($min+$max)/2);
} else {
  $end = 1;
}

}

$end = 0;
while($end == 0){
  $query = sprintf("SELECT id, date_time FROM date_table where id=%d", $id);
  $result = mysqli_query($conn, $query);
  $row = mysqli_fetch_row($result);
  $row[1] = substr($row[1], 0, 10);
if($row[1]==$date){
  $max = $id;
  $id = round(($min+$max)/2);
} else {
  $min = $id;
  $id = round(($min+$max)/2);
}

if($max==$min+1){
  $end = 1;
}

}

echo $id;

?>
  </body>
</html>


결과는 다음과 같다.



2018-01-15가 처음 등장하는 id는 229번이다.



허전하다면 while문 안쪽에 id를 찾아가는 과정을 보여주도록 echo문을 넣어도 좋다.


<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <title></title>
  </head>
  <body>

<?php

$query = 'SELECT max(id) FROM date_table';
$result = mysqli_query($conn, $query);
$row = mysqli_fetch_row($result);
$max = $row[0];
$min = 1;
$date = '2018-01-15';

$id = round(($min+$max)/2);

$end = 0;
while($end == 0){

  echo $id,"<BR>";

  $query = sprintf("SELECT id, date_time FROM date_table where id=%d", $id);
  $result = mysqli_query($conn, $query);
  $row = mysqli_fetch_row($result);
  $row[1] = substr($row[1], 0, 10);
if($row[1]>$date){
  $max = $id;
  $id = round(($min+$max)/2);
} else if($row[1]<$date){
  $min = $id;
  $id = round(($min+$max)/2);
} else {
  $end = 1;
}

}

$end = 0;
while($end == 0){

  echo $id,"<BR>";

  $query = sprintf("SELECT id, date_time FROM date_table where id=%d", $id);
  $result = mysqli_query($conn, $query);
  $row = mysqli_fetch_row($result);
  $row[1] = substr($row[1], 0, 10);
if($row[1]==$date){
  $max = $id;
  $id = round(($min+$max)/2);
} else {
  $min = $id;
  $id = round(($min+$max)/2);
}

if($max==$min+1){
  $end=1;
}

}

echo $id;

?>
  </body>
</html>


결과는 다음과 같다.



251이 두 번 나타나는 것으로 보아


첫 Binary Search로 2018-01-15에 해당하는 아이디는 단 두 번 만에 찾고, 


두 번째 Binary Search로 2018-01-15에 해당하는 첫 번째 아이디를 찾아가는 것을 볼 수 있다.



조금 더 찾기 힘든 날짜로 설정해 보자.


$date = '2018-02-28' 로 실행하면 다음과 같다.




첫 Binary Search 는 7번 만에 993에서 확신하고, 이후로 범위를 좁히는 것을 볼 수 있다.





반응형

'PHP' 카테고리의 다른 글

[PHP] $i++ 과 ++$i 의 차이  (0) 2018.06.21
[PHP] 에러메시지 Undefined offset 의미  (0) 2018.06.20
[PHP] 회원들의 재구매율 알아보기(4) - 완성  (0) 2017.10.13
[PHP] 회원들의 재구매율 알아보기(3) - 날짜 계산하기 strtotime()  (0) 2017.09.26
[PHP] 회원들의 재구매율 알아보기(2) - 두 배열 비교하기 in_array()  (0) 2017.09.25
[PHP] 회원들의 재구매율 알아보기(1) - MySQL 컬럼(열)을 배열로 만들기  (0) 2017.09.24
[PHP] mysqli_fetch_row, assoc, array 의 차이  (4) 2017.09.20
[PHP] DB에서 특정 행들만 가져오기(8) - DB 에서 열 이름 가져오기  (0) 2017.09.19
[PHP] DB에서 특정 행들만 가져오기(7) - DB에서 가져온 정보 출력하기 mysqli_fetch_row()  (0) 2017.09.18
[PHP] DB에서 특정 행들만 가져오기(6) - 쿼리 작성하기 mysqli_query()  (0) 2017.09.17

관련글

댓글

티스토리툴바