b-tree 놈은 이진트리 형태로 이것 아니면, 저것으로 움직입니다. 그래서, 그 키와 완벽하게 일치해야합니다. (이렇게 보면, hash와 크게 다르지 않지요, 이놈이 hash와 크게 다른 것은 키의 접근 방식이 순차적입니다.)
즉, "10보다 큰놈 모두 뽑아라."
이렇게 했을 경우, 10을 찾고 그 왼쪽 트리의 모든 것을 그 다음부터 끝까지 아무 생각 없이 뽑아내면, 되는 식입니다.
하지만,
"10을 찾아라." 이런 식으로 1:1 형태의 검색만 사용된다면,(죽어도 끝까지 이런 검색만 사용된다면) b-tree보다는 hash 인덱싱이 훨씬 빠릅니다.
한변, r-tree 놈은 그 알고리즘은 공부안해서 모르겠지만,
배열의 중간놈도 인덱싱을 가능하게 해줍니다.
이말이 무슨 말인고 하면,
"{1,2,3,4}" 이런 자료가 있을때, "3"이 들어있는 배열 모두 찾아라. 이렇게 했을때, 인덱싱을 사용하게 하는 놈입니다. (어떻게해서 그렇게 되는지는 모르겠습니다. 공부해야지)
(물론 PostgreSQL에서 그냥 R-Tree 쓰겠다고 배열의 인덱싱이 가능한 것은 아닙니다. PostgreSQL에서의 배열 자료형에 대한 인덱싱은 따로 존재합니다. 이곳 투토리얼 참조)
그래서, r-tree 놈은 gis쪽으로 많이 사용된다네요. (제가 gis 쪽은 전혀 관심이 없어서) 또한 이놈의 확장형태로 gist 라는 인덱싱이 있는데, 이놈은 PostgreSQL에서 contrib 모듈형태로 제공합니다. 이놈이 바로 제가 쓰는 배열 관련 인덱싱, 날짜관련 인덱싱에서 사용됩니다.
-------
다음 text 자료형의 중간자 검색 ~* 놈이나, like에서의 '%검색어%' 이런 쿼리는 당연히 인덱싱이 불가능합니다. 이글 제일 처음에서 이야기한 btree 인덱싱을 사용하기 때문입니다.
제가 제일 관심 가지는 부분중에 하나인데,
이곳 게시판에서 full text 검색 관련 검색을 해보시면,
그에 대한 자세한 이야기가 있습니다.
아주 복잡한 문제인지라, 이곳에서는 언급하기가 힘드네요.
현재로써는 한국어 환경에 대한 full text 인덱싱은 PostgreSQL에서 제공하는 것을 아직 못봤습니다. (반드시 이루워내야할 숙원사업 -.-)
관심있으신 분의 적극참여를 ^.^
|