BTree

진리는어디에 2008. 3. 26. 00:49

구현 완료

  • Insert
    • split
  • delete
    • merge
  • search

미구현
 iterate
잠이 오긴 하지만 잠시 생각 해보자.
Btree는 iteration이 상당히 까칠하다. 그럼 list를 추가하면 될듯한데..그럼 키는 트리에 유지하고 값만 리스트에 저장 하면 되겠군. 그런데 문제는 트리가 다시 밸런스를 맞추면서인데..예를 들어 2:2가 들어 오고 3:3이 들어 오고 1:1이 들어 오면 3이야 뒤에 추가 하면 되니 아무런 문제가 없지만 1:1은 2보다 작다는 것을 알 수 있으니까 2의 iterator 앞에 넣어 주면 되겠군. 대충 돌아 갈 수 있을 것 같구먼
 erase

소스 코드 :




'진리는어디에' 카테고리의 다른 글

Generation reference counting  (0) 2008.05.15
Logical clock  (2) 2008.05.02
BTree  (8) 2008.03.26
Python embedding 1 - Overview  (6) 2008.03.13
파이썬으로 utf-8 문서 읽기  (1) 2008.02.22
Python embedding 4 - PyErr_Print() 를 파일로 남기기  (4) 2008.02.15
Posted by kukuta

댓글을 달아 주세요

  1. Favicon of http://blog.ggamsso.wo.tc BlogIcon 깜쏘 2008.02.24 23:47  댓글주소  수정/삭제  댓글쓰기

    연구실 검색엔진에 쓰고 있는 b+tree가 생각나네요 ^^;;
    bucket, cache, merge가 절 괴롭힙니다.

    • Favicon of https://kukuta.tistory.com BlogIcon kukuta 2008.02.25 10:31 신고  댓글주소  수정/삭제

      이터레이션이 문제야..-_-;
      stack을 안 쓰고 트리를 이터레이션 할 수 있는 방법이 없을까?
      물론 성능 저하도 그렇게 크게 없어야 하고 말이야.

    • Favicon of http://blog.ggamsso.wo.tc BlogIcon 깜쏘 2008.02.26 01:27 신고  댓글주소  수정/삭제

      b-tree에서는 문제가 되겠지만, leef-node가 전부 연결되어 있는 b+tree를 사용하면 간단하게 해결되잖아요.
      그 대표적인 개발 예가 버클리DB
      db로부터 cursor을 받아서 next() 메쏘드로 iteration하면 끝나는 이야기 아닌가요?
      뭐, 선배가 저렇게 구현을 해야 하지만...

    • Favicon of https://kukuta.tistory.com BlogIcon kukuta 2008.02.26 19:20 신고  댓글주소  수정/삭제

      아놔...첨엔 이렇게 쓸 생각 안 했었지..
      그냥 주말에 하도 할 일이 없어서 옛날에 배웠던거나 만들어 볼까하다가, 만들다 보니 stl하고 비슷하게 만들자..라는 생각까지..쿨럭

      니 말대로 다 엎고 다시 B+트리 만들어야 겠다.

    • Favicon of http://blog.ggamsso.wo.tc BlogIcon 깜쏘 2008.02.26 23:16 신고  댓글주소  수정/삭제

      필요하세요? C는 있는데...

    • Favicon of https://kukuta.tistory.com BlogIcon kukuta 2008.02.27 16:02 신고  댓글주소  수정/삭제

      필요하지는 않아. 무슨 프로젝트가 걸린게 아니고 그냥 주말에 심심해서 하는 일이니까..-_-;

      너한테 코드를 받아버리면 주말에 난 뭐하니?

    • Favicon of http://blog.ggamsso.wo.tc BlogIcon 깜쏘 2008.03.03 13:29 신고  댓글주소  수정/삭제

      할 거 많아요.
      제가 소스를 드린 만큼 저랑 놀아주셔야죠.

    • Favicon of https://kukuta.tistory.com BlogIcon kukuta 2008.03.03 21:26 신고  댓글주소  수정/삭제

      위키피디어나, 소스포지가면 소스 넘쳐 흘러..ㅋ
      그리고 너랑 안놀아~
      울 엄마가 남자 좋아하는 애랑은 놀지 말래