findRunStart 的介紹在投影片中沒有非常詳細
大致上就是 new_scan的其中一部分
去找 lo_key 所在的 page 和 rid
引述上一屆助教的回文
※ 引述《TimeString (時弦 - 我要DJmax的pc版!)》之銘言：
: Hi 同學，
: findRunStart 簡單的講就是找某一個 key，
: 它是在哪一個 (BTLeaf) page 裡，且 page 裡的哪一個 RID 可以找到這個 key。
: 所以 findRunStart 所傳入參數，
: 第一個 lo_key 為 input，代表你要找的 key；
: 第二個 pppage 可視為 output (所以這就是為什麼他宣告成指標的型態)，
: 回傳 key 所在的 page 在哪；
: 第三個 pstartrid 可視為 output，回傳所屬的 RID。
: 在整個 btree 中，findRunStart 是這樣被使用的：
: 我們想要找 btree 裡的某一段 data，
: 所以會有 low key 與 high key 來 bound 住我們要搜尋的範圍。
: new_scan() 是一個使用 findRunStart() 的最典型例子，
: new_scan() 傳入 lo_key 及 hi_key，
: 而使用 findRunStart() 來尋找 lo_key 在 btree 裡的哪一個 page 及 RID，
: 這也是為什麼 findRunStart() 第一個參數特別命名為 "lo_key" 而不是 "key"。
: 且為什麼這個函式叫作 findRun"Start"。
: 但這時或許大家馬上就想到，為什麼我們不用找 hi_key 在哪個 page 及 RID?
: 因為 b+ tree 的最後一層是 linked list!!
: 感謝同學的提問!
對於 new_scan 的介紹如下
new_scan
create a scan from lo_key to hi_key, but what you have to do is find the
lo_key in leafPages. It will call scan->get_next() after calling this.
Set up:
1.store the leafPage where the record with lo_key located in scan->leafp
2.store the RID of record with lo_key in scan->curRid
3.store the hi_key in scan->endkey
findRunStart
Find the RID and leafPage of the record with lo_key
findRunStart Todo的詳細一點介紹
while (ppagei->get_type() == INDEX) {
// find left-most occurrence of `lo_key', going all the way left if *lo_key
is NULL.
// That is, find the leafPage ppagei that contains the record with lo_key
}
while (st == NOMORERECS) {
// If ppage you just found before has no records, you should find the next
// page until it has records
}
while (keyCompare(&curkey, lo_key, key_type) < 0) {
// find the RID of record matched lo_key, and store in metaRid
}
其實我也只是早點寫這份作業的學生
有許多問題我當時也沒注意到
有任何問題我盡可能幫忙
雖然我沒有回的很快
-TA 葉俊言