대규모 데이타 관리 자료구조...

bigbaby의 이미지

안녕하세요...

대규모 데이터를 관리하는 자료구조를 만드려고 합니다.

대략 10만~50만 정도의 노드 갯수를 갖을 예정입니다.

그리고, 각 노드마다 최소 1초 간격으로 타임 아웃 체크를 해서 자료구조에서 제거해야하며,

삽입/삭제/검색이 빨라야합니다.

가장 큰 문제는 노드 갯수가 상당히 많아서, 타임아웃 시 정렬되지 않으면 풀 검색을 해야하는데

좋은 방법이 잘 떠오르지 않네요...

만약 시간 순 정렬을 해놓는다고 하면, 검색할 때 느려질거라 생각이 됩니다.

이 경우 어떤 방법이 좋을까요? 좋은 자료구조 없을까요>

nthroot의 이미지

balanced tree

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

irongate의 이미지

용도에 따라 다르게 자료 구조를 만들어서 관리하는게 좋을 듯 합니다.

단순히 타임 아웃만 관리 한다면 시간 순으로 정렬해서 타임 아웃이 예상 되는 시간 위치에 저장해 놓고,
그 시간이 되어서 검사해야 하는 노드만 검사 하면 좀더 적은 갯수를 검사해도 됩니다.

동일한 노드를 다른 조건에 의해서 검색해야 한다면 그에 맞는 자료 구조를 사용해서 노드를 정렬하는게 좋구요.
결국 이렇게 되면 동일한 노드가 여러개의 자료 구조에 매달릴수 있는데,
이는 구조만 잘 잡으면 별 문제 없을듯 하네요.

제가 타임 아웃과 복잡한 키의 조합에 의한 검색을 이와 같이 분리해서 구현 했습니다.
최대 수는 250만 노드.... 물론 250만개가 1초 이내에 생성 되면 이론의 베이스가 망가지긴 합니다. ㅋ
타임아웃을 위해서 250만 노드를 모두 뒤지거나 삽입시 정렬하는 것은 정말 많은 부하가 예상 되죠....

이 아이디어는 리눅스 커널의 타이머 이벤트 처리 부분에서 힌트를 얻었습니다.

imposno의 이미지

B+ TREE ??

소타의 이미지

10만~50만의 노드라는게 데이터의 갯수가 아니라 클러스터 노드인가요?;; 10만~50만이면 대규모 데이터라고 하기엔 좀 작아서요.

10만~50만의 데이터를 키로 탐색도 해야 하고 시간순 정렬도 필요하다면 저도 B+tree추천이요.

clique의 이미지

10~50만 개 정도면 범용 dbms를 써도 커버가 될법하네요. 그래도 좀 늦다고 생각하시면 berkeley db 같이 가벼운 녀석을 생각해 보시면 됩니다.

neocoin의 이미지

10~50 만에 key base 면 범용 db 도 충분할 것 같고 (메모리만 되면 어차피 몽땅 다 메모리에 올라가겠죠.)

conch db나 mongo db 도 괜찮을 듯합니다.
트리 구현해서 쓰면 차후 관리하기가 귀찮아지죠.

메모리에 상주해서 돌리면 뭐 memche 나 redis 면 날아갈듯 합니다.

bigbaby의 이미지

답변 감사합니다. ^^

10~50만개 데이터는 제가 정의한 구조체들의 갯수입니다.

처음 보지만 좋은 오픈 소스도 많이 있네요...

성능상의 이유로 db는 사용하지 않습니다. ^^;

메모리에 올라가는 자료구조에 대한 질문이었습니다.

memche나 redis 는 검색해보니 상당히 좋은거 같지만 바로 사용하기에는 시간이 없어 힘들것 같습니다. ^^;

B+ 트리는 좋을거 같긴한데...직접 구현해야되지 않을가요?? ㅠㅠ 아니면 오픈 소스로 있나요?

C 기반이라 자료구조를 가져다 쓰기가 힘드네요..

madman93의 이미지

http://www.google.com/codesearch?hl=ko&lr=&q=B%2Btree+lang:c&sbtn=%EA%B2%80%EC%83%89

---------------------------------------------
git init
git add .
git commit -am "project init"
---------------------------------------------

---------------------------------------------
git init
git add .
git commit -am "project init"
---------------------------------------------

댓글 달기

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
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.