考慮一個磁碟檔案 $\mathcal{F}$，其中儲存一組鍵值對（key-value pairs）。API「$y = READ(x)$」用來回傳鍵 $x$ 對應的值 $y$，前提是鍵值對 $(x,y)$ 存在於 $\mathcal{F}$ 中。API「$WRITE(x,y)$」則是：若 $(x,y)$ 不存在，就把它寫入 $\mathcal{F}$；否則就用 $y$ 更新鍵 $x$ 的值。這裡的 $READ(\cdot)$ 與 $WRITE(\cdot)$ 是各自獨立的行程（或執行緒）。請針對以下設計，判斷正確（○）或錯誤（×），這些設計的目的是在（存取延遲的意義下）最佳化對檔案 $\mathcal{F}$ 的讀寫操作。令 $S$ 為儲存在 $\mathcal{F}$ 中的鍵值對集合。

(a) 將 $S$ 分割成數個互不相交的區塊（blocks）$\{s\}$，即 $S = \bigcup \{s\}$。每個區塊 $s \in S$ 是記憶體與磁碟子系統之間的擷取單位（fetching unit）。給定 $(x,y) \in s$，配置一個記憶體區塊 $m$ 來儲存從磁碟複製過來的 $s$。接著從 $m$ 中取出 $(x,y)$ 並回傳給 $READ(\cdot)$。為了效率，$m$ 中的鍵應該用平衡搜尋樹（balanced search tree）之類的結構組織。

(b) 對於 $WRITE(\cdot)$，先更新 $m$ 中的 $(x,y)$。當 $m$ 被置換（replaced）時，$m$ 應寫回 $\mathcal{F}$，且 $\mathcal{F}$ 中原本的 $s$ 可以被覆蓋。

(c) 我們額外在檔案系統中建立一個本機檔案索引 $\mathcal{I}$，用來在 $S$ 中定位 $(x,y)$，也就是說 $\mathcal{I}$ 能協助快速判斷 $(x,y)$ 儲存在哪一個 $s \in S$ 中。$\mathcal{I}$ 會被複製一份到記憶體中（記為 $\mathcal{I}^*$），以減少對磁碟子系統執行的 IO 操作數量。$\mathcal{I}^*$ 會因為 $WRITE(\cdot)$ 新增的 $(x,y)$ 而被更新。因此，$\mathcal{I}^*$ 與 $\mathcal{I}$ 可能會不一致。

(d) 有可能發生多個 $WRITE(\cdot)$ 操作處理相同的鍵 $x$，且這些 $WRITE(\cdot)$ 操作可能由不同的客戶端（clients）並行呼叫。一種可能的實作方式是：每個 $WRITE(\cdot)$ 必須先成功取得存取 $m$ 與 $\mathcal{I}^*$ 兩者所需的鎖（locks），才能繼續更新 $x$ 的值；一旦值被提交（committed），兩個鎖都會被釋放。在這種實作方式下，各種 $WRITE(\cdot)$ 操作『不可能』因此產生死結（deadlock）。