darigold 2017-1-16 02:00
繼 debugger 之後又一新嘗試。一直想寫 B+ tree，但係都冇郁手，而家開始郁手了。
計劃先從 in memory B+ tree (fix size key/value)開始，再寫 memory - disk serialization ，buffer manager 等等。
因為唔熟悉，慢慢黎 ……
Andylaubobby 2017-1-16 03:15
[quote]原帖由 [i]darigold[/i] 於 2017-1-16 02:00 AM 發表 [url=http://www.discuss.com.hk/redirect.php?goto=findpost&pid=454872068&ptid=26384058][img]http://www.discuss.com.hk/images/common/back.gif[/img][/url]
繼 debugger 之後又一新嘗試。一直想寫 B+ tree，但係都冇郁手，而家開始郁手了。
計劃先從 in memory B+ tree (fix size key/value)開始，再寫 memory - disk serialization ，buffer manager 等等。
因為唔熟 ... [/quote]
推
I always find embedded database interesting. Is it sql or nosql? They said Kyoto cabinet license fee is 15000.
http://stackoverflow.com/questions/2403174/is-there-any-nosql-database-as-simple-as-sqlite
煙民母親生賤種
*** 作者被禁止或刪除 內容自動屏蔽 ***
darigold 2017-1-16 03:56
[quote]原帖由 [i]煙民母親生賤種[/i] 於 2017-1-16 03:19 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=454873600&ptid=26384058][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
多口問句, 係咪俾人炒左! :fst_013:
[/quote]
當然冇 …… 你俾人抄左會手痕寫 open source ？
darigold 2017-1-16 03:58
之前冇 post code link ，project 係呢度︰
[url]https://github.com/cshung/MiscLab/tree/master/MingDatabase[/url]
從零開始，岩岩先開始寫 btree insertion ……
darigold 2017-1-16 09:39
寫好了 b+ tree 的 insert。
現在明白為甚麼我們總是 split 向右，方便啊 …… ！
Susan﹏汪汪 2017-1-16 10:22
memory - disk serialization打算點做？
darigold 2017-1-16 11:05
[quote]原帖由 [i]Susan﹏汪汪[/i] 於 2017-1-16 10:22 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=454881314&ptid=26384058][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
memory - disk serialization打算點做？
[/quote]
fread() / fwrite()
話時話，bool select(int key, int* result) 已經寫好 push 左。
[[i] 本帖最後由 darigold 於 2017-1-16 11:07 AM 編輯 [/i]]
Susan﹏汪汪 2017-1-16 12:49
因為如果用mmap的話
應該要由memory allocation 寫先
std library的vector同map都冇得用
煙民母親生賤種
*** 作者被禁止或刪除 內容自動屏蔽 ***
darigold 2017-1-17 01:55
[quote]原帖由 [i]煙民母親生賤種[/i] 於 2017-1-16 11:45 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=454917597&ptid=26384058][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
唔係邊有咁多時間? :fst_013:
[/quote]
今日放假:smile_o10:
[url=https://en.wikipedia.org/wiki/Martin_Luther_King_Jr._Day]https://en.wikipedia.org/wiki/Martin_Luther_King_Jr._Day[/url]
唔知道之前有冇 post 過呢個故事︰
[img]http://4.bp.blogspot.com/-ekYv4pNlCG4/VEaOaJUjGkI/AAAAAAAAIG4/kBx1ECJW8ow/s1600/75031_578540665539337_2092727763_n.jpg[/img]
其實某程度上，我們和這隻老鼠一樣，如果一直只想著食老本行，最終就會好似呢隻老鼠咁，坐食山空。
所以有時候花些時間去做一些其它的事，就好似買保險一樣。寫 compiler 寫多了，學下寫 database 也不錯。
煙民母親生賤種
*** 作者被禁止或刪除 內容自動屏蔽 ***
darigold 2017-1-17 02:24
[quote]原帖由 [i]煙民母親生賤種[/i] 於 2017-1-17 02:17 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=454922440&ptid=26384058][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
真是一個很好的故事!! :fst_004:
[/quote]
哈哈，米缸裏的米當然要吃！只是別吃到跳不出去罷了。
學點別的東西，就像搭條縄子一樣，是個後備而已 ……
darigold 2017-1-17 09:22
B+ tree delete 真係好鬼難寫 …… :smile_o16:
darigold 2017-1-18 13:32
終於寫到 B+ tree deletion。
比 insertion 複雜好多 ……
stupidsing 2017-1-18 16:43
寫過。
https://github.com/stupidsing/suite/blob/df552e8a1efd58317fd8459542ef1dbff0f198ed/src/main/java/suite/btree/impl/B_TreeImpl.java
deletion 時不平衡是向左右找兄弟做合併，然後向上一層 傳遞。
反而我唔理解紅黑樹，雖然兩者 (vs 2-3 tree) 好似係對應的。
都唔知咩人會諗到紅色黑色咁多 rules 出黎既。
得閒寫埋 persistent 版本，不過唔知點樣有效 gc unused pages.
煙民母親生賤種
*** 作者被禁止或刪除 內容自動屏蔽 ***
darigold 2017-1-19 12:18
[quote]原帖由 [i]stupidsing[/i] 於 2017-1-18 04:43 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=455001836&ptid=26384058][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
寫過。
[url=https://github.com/stupidsing/suite/blob/df552e8a1efd58317fd8459542ef1dbff0f198ed/src/main/java/suite/btree/impl/B_TreeImpl.java]https://github.com/stupidsing/suite/blob/df552e8a1efd58317fd8459542ef1dbff0f198ed/src/main/java/suite/btree/impl/B_TreeImpl.java[/url]
deletion 時不平衡是向左右找兄弟做合併，然後向上一層 傳遞。 ...
[/quote]
你的實現和我想寫的很類似。我才剛起步寫B+ tree，你這個連 page manager 都有了。
我的 deletion 也是左右找 key 借，沒有的話再 merge 。
C++ 的確比 Java 麻煩 …… 我寫了快 700 行才剛寫好 select/insert/delete into B+ tree
不過我應該有不少 duplicated code 。
darigold 2017-1-19 12:21
[quote]原帖由 [i]煙民母親生賤種[/i] 於 2017-1-19 03:07 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=455029313&ptid=26384058][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
請問上面堆野寫左幾耐?
(in hours please) :fst_007:
[/quote]
Stupidsing 兄用左幾多時間寫我唔知，但係我就用左三日 ……
當然斷斷續續又番工又睇電視，得閒諗起先 commit/push 一次，有時候諗到 idea 寫句 comment 又 commit ……
stupidsing 2017-1-19 20:27
點會記得呢，同埋係斷斷續續放工寫少少，得閒又 refactor 少少。
寫果時唔明個原理，幾星期都有，而家明左再寫會快好多。
darigold 2017-1-20 08:44
[quote]原帖由 [i]stupidsing[/i] 於 2017-1-19 08:27 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=455067915&ptid=26384058][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
點會記得呢，同埋係斷斷續續放工寫少少，得閒又 refactor 少少。
寫果時唔明個原理，幾星期都有，而家明左再寫會快好多。
[/quote]
再寫就冇乜意義了。哈哈，個人來說，只為享受「終於想通」個殺那既興奮 ……
做已經識做既野好大程度上只係工作，番工要做咪做囉，私人，當然唔做啦，做黎做乜？
block 左一個問題諗幾星期我諗我冇咁既耐性 ……
話時話，我又向前走左一小步，岩岩 push 左個 change 去 maintain right sibling pointer。
下一步打算做 randomized testing 。
Susan﹏汪汪 2017-1-20 09:14
[quote]原帖由 [i]darigold[/i] 於 2017-1-20 08:44 AM 發表 [url=http://www.discuss.com.hk/redirect.php?goto=findpost&pid=455088183&ptid=26384058][img]http://www.discuss.com.hk/images/common/back.gif[/img][/url]
再寫就冇乜意義了。哈哈，個人來說，只為享受「終於想通」個殺那既興奮 ……
做已經識做既野好大程度上只係工作，番工要做咪做囉，私人，當然唔做啦，做黎做乜？
block 左一個問題諗幾星期我諗我冇咁既耐性 ... [/quote]
哈
汪汪斷斷續續咁寫左一年Weiler Atherton algorithm
到而家都仲寫緊、呢排有新突破
琴日終於寫到卡左好耐嘅位
darigold 2017-1-20 11:15
[quote]原帖由 [i]darigold[/i] 於 2017-1-20 08:44 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=455088183&ptid=26384058][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
……
話時話，我又向前走左一小步，岩岩 push 左個 change 去 maintain right sibling pointer。
下一步打算做 randomized testing 。
[/quote]
randomized testing 真係正，又搵到 bug 。尤其係寫 data structure ， 呢招非常方便有效 ！
個 program 唔係好大，應該唔難 debug 。
darigold 2017-1-20 12:28
[quote]原帖由 [i]darigold[/i] 於 2017-1-20 11:15 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=455094919&ptid=26384058][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
randomized testing 真係正，又搵到 bug 。尤其係寫 data structure ， 呢招非常方便有效 ！
個 program 唔係好大，應該唔難 debug 。
[/quote]
簡單 bug ，fixed ，oh yeah !
:smile_o10:
stupidsing 2017-1-20 21:20
寫左段 code 一排之後睇返，見到唔順眼的地方執返佢，行得唔快 tune 下佢，都好有趣。愈黎愈精煉。
日久又會有其他發現，又或者引用人地的寫法黎改，原來咁寫好Ｄ喎。
反而做習題咁寫完就扔，唔係好鍾意。
darigold 2017-1-21 13:02
OT 一下自己先 …… TypeScript 好似好好玩 …
煙民母親生賤種
*** 作者被禁止或刪除 內容自動屏蔽 ***
stupidsing 2017-1-22 09:38
我覺得 rdbms 戲玉係個 transaction manager, 點樣做 read committed / repeatable
read / serializable.
有Ｄ似寫 STM, 不過係磁碟上做 locking.
幾萬種 js variant 撈到亂晒 @_@
darigold 2017-1-23 23:05
搞掂 TypeScript 後，番黎砌 database 。
下一步既目標係 serialize to disk ，我希望 btree 可以直接 access page memory 而不用 copy to vector ，所以最近搞左 d refactoring ，希望可以簡化。
同時我想支持 variable size key / value ， 好 challenging ……
darigold 2017-1-26 13:14
最近很忙，很勉強做了一點點 refactoring ...