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 叶俊言