DB에서 단편화 현상과 무작위 INSERT에 대해 여쭤봅니다.

winner의 이미지

제가 알기로는 균형트리들은 트리의 한쪽 끝에 계속해서 삽입될 때 치우침 현상이 일어납니다.
이것은 B tree에서도 마찬가지라서 위와 같은 현상이 발생할 경우 대부분의 노드들은 50%만 채워질 것입니다.

그렇다면 자동증가수(Auto increment 혹은 IDENTITY 혹은 Sequence)를 index로 지정하면 위와 같은 현상이 일어나지 않을까요?
또한 그렇다면 무작위로 삽입되는 키를 index로 지정하는 것이 index 재구축을 하지 않는 경우 공간효율성 측면에서는 유리할 것으로 판단됩니다.

저는 index 단편화(fragmentation)라는 용어가 위와 같이 index node들의 공간효율이 떨어지는 상황으로 알고 있습니다.
제가 이 용어를 정확히 아는 것이 맞나요?

nthroot의 이미지

------식은이 처------
길이 끝나는 저기엔 아무 것도 없어요. 희망이고 나발이고 아무 것도 없어.

소타의 이미지

균형 트리들이 그런다기 보다는 B-tree, B+tree, B*tree 같이 하나의 노드에 여러개의 데이터가 매달리는 종류들이 그렇게 되네요.
저도 B+tree를 구현하면서 그런 단편화를 심각하게 겪었는데 노드를 나눌 때 최대한 조금만(1~10%) 쪼개서 노드를 새로 만들고 나누기 전에 다음 노드를 보고 공간이 있으면 같은 양을 토스해주는 식으로 단편화를 많이 줄일 수 있었습니다. 이전 노드도 보고 같은 짓을 하면 더 줄일 수 있겠지만 하진 않았네요;;

Quote:
그렇다면 자동증가수(Auto increment 혹은 IDENTITY 혹은 Sequence)를 index로 지정하면 위와 같은 현상이 일어나지 않을까요?
또한 그렇다면 무작위로 삽입되는 키를 index로 지정하는 것이 index 재구축을 하지 않는 경우 공간효율성 측면에서는 유리할 것으로 판단됩니다.

이건 어떤 의미인지 궁금합니다; 제가 이해를 못 하는 것인지..
winner의 이미지

자동증가수는 새로운 행이 삽입될 때 마다 최대수가 삽입될 겁니다. 그렇다면 삽입될 때 인덱스 트리의 한쪽 끝에서 계속 삽입할려고 할텐데요. 그리고 당연히 트리의 치우침 현상이 발생하지 않겠냐는 거죠.

무작위 수에 인덱스가 지정되면 오히려 균등하게 흩뿌리는 경향으로 인덱스 노드 분리가 적게 발생하지 않을까라는 의문이 들었습니다. 자동증가수가 인덱스로 지정되어 있다면 인덱스 노드 분리가 발생할 때 50:50 으로 분리하지 않고, 100:0 으로 분리해야 하지 않을까 그런 생각이 든거죠. 그리고 DBMS가 이 방식을 쓰는가라는 질문이고요. 말씀하신 1~10%가 fill factor 옵션을 통해 지정되는 것인가요? 그것은 아닌 것 같은데 말이죠. 제가 알기로 그것은 처음 인덱스 구축할 때 쓰는 것으로 알고 있습니다. 운영과정에서 새로운 행이 삽입되어 인덱스가 분리될 때도 그 비율이 사용되나요?

더욱 큰 문제는 상황에 따라서 값은 분명 자동증가수이지만 DBMS가 생성을 관리하지 않는 경우입니다. 그런 경우에 DBMS는 지능적으로 대처할 방법이 없을텐데요.

음... nthroot님의 링크를 읽어보니 제가 질문한 것은 내부단편화(Internal Fragmentation)이고, fill factor는 인덱스 노드분리에 사용되기 때문에 자동증가수에 대해서는 fill factor를 크게 지정해줘야 하는 것 같네요. 제가 제대로 이해한 것이 맞나요? 왠지 틀린 것 같아요.
만일 그렇다면 자동감소수에 대해서는 fill factor는 낮추면 분리되는 오른쪽 노드에 몰려야 하는데 그것은 아닌 것 같고...

소타의 이미지

이해하신게 맞습니다. 인덱싱 할 데이터들의 특성에 따라 자료 구조를 선택해야 하는데 선형적으로 일정하게 증가하는 데이터가 있다면 b-tree 계열은 잘못된 선택일 수 있습니다. 이런 종류의 데이터는 fill factor를 100으로 해도 자료 구조 자체를 유지하기 위해서 들어가는 자원이 아깝죠; 다른 인덱스 종류를 선택하는 게 좋습니다.

저는 DB엔진을 만드는 업무를 합니다.
예전에 선형적인 데이터를 위한 DB엔진을 만들 때는 그냥 파일 하나 만들고 mmap으로 매핑해서 통째로 배열을 만들어서 썼습니다. 파일 크기가 메모리보다 작아서 버퍼캐시에서 처리할 수 있을 때는 쓸만하지만 그렇지 않으면 어차피 재앙이 찾아옵니다. 큰 파일을 mmap으로 처리하는게 잘못된 선택이기도 했죠;;

최근까지는 데이터의 키가 랜덤 수준은 아니지만 들쭉날쭉한 데이터를 위한 DB엔진을 만들었습니다. 디스크에 친화적인 자료구조 중 하나가 b+tree 계열인데 이 놈도 가능하면 데이터를 빡빡하게 넣어서 locality를 높이는게 goal 중에 하나입니다. 그래서 fill factor를 높게 잡고 쪼개기 전에 꼼수로 어디 던져줄 데 없나 근처 노드들을 살피는거죠;
그래야 버퍼캐시에 최대한 많이 넣어서 disk IO를 줄일 수 있으니까요.

범용 DBMS중에 인덱스 생성 후에 fill factor를 지정할 수 있는 놈 중엔 postgresql이 있습니다. fill factor를 바꾸면 새로 인덱스 하는지는 모르겠습니다만 postgresql은 인덱스 재 생성 시 테이블 락을 걸지 않으므로 어찌 됐든 좋습니다.
http://www.postgresql.org/docs/8.2/static/sql-alterindex.html

sql2의 이미지

인용:


그렇다면 자동증가수(Auto increment 혹은 IDENTITY 혹은 Sequence)를 index로 지정하면 위와 같은 현상이 일어나지 않을까요?
또한 그렇다면 무작위로 삽입되는 키를 index로 지정하는 것이 index 재구축을 하지 않는 경우 공간효율성 측면에서는 유리할 것으로 판단됩니다.

정답은 애매하게도 "DB DB마다 달라요" 일겁니다.

과연 키가 자동으로 일정하게 증가하는 걸 뻔히 알고 있는데 이런 특정케이스에 대해서 그냥 인덱스를 생성할까요? 그럴수도 아닐수도 있겠죠. DBMS 마다 각각의 인덱스 정책이 있을테니 그걸 확인해봐할 겁니다.

그리고, 키는 말 그대로 키(?)값이기 때문에 그냥 랜덤한 값을 쓸 경우가 많을까요?

대부분의 DBMS가 DB 혹은 인덱스를 재구성(구축)할 것을 권장하는 걸로 알고 있습니다.

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.