布隆過濾器
布隆過濾器是一種數(shù)據(jù)結(jié)構(gòu)，概率性數(shù)據(jù)結(jié)構(gòu)，高效的插入與查詢，回答的一定不存在或者可能存在。相比List, Set, Map更高效，占用空間少，但返回結(jié)果是概率的。
用HashMap判斷某個元素是否存在當然是高效的O(1)，但是哈希表占用空間大，而且不能充分利用空間，所以在數(shù)據(jù)集大時可能無法一次性讀入內(nèi)存構(gòu)建HashMap。
布隆過濾器是一個Bit向量，如有8位，三個哈希函數(shù)，如百度哈希生成1,4,7，阿里哈希成2,4,8，把相應(yīng)的位置1，這時查詢頭條(哈希值347)-3是0,頭條顯然一定不在，但某個公司哈希值為148雖然都是1，但這是可能存在。
布隆過濾器需要考慮哈希函數(shù)的個數(shù)k，和bit向量的長度m，有公式
用在減少磁盤I/O或磁盤請求，一個值一定不存在就可不在進行后續(xù)的查詢請求。
Larger-than-Memory Databases
對于大于內(nèi)存的內(nèi)存數(shù)據(jù)庫而言，允許讀寫磁盤上的數(shù)據(jù)，但是和面向磁盤的數(shù)據(jù)還是有所不同的。
內(nèi)存存儲=面向元組
磁盤存儲=面向塊
OLAP經(jīng)常需要訪問整個表，仍要用面向磁盤的緩沖池進行處理
For OLTP
OLTP通常會有熱數(shù)據(jù)和冷數(shù)據(jù)，這時候就需要一種機制把冷數(shù)據(jù)移到磁盤中并在需要的時候能對它進行檢索。
需要解決的問題：
運行時的操作怎么區(qū)分冷數(shù)據(jù)，用什么方式來分辨數(shù)據(jù)是不是冷的；驅(qū)逐策略，何時驅(qū)逐，被驅(qū)逐的元組通過什么方式訪問(驅(qū)逐元數(shù)據(jù))；數(shù)據(jù)的檢索策略，檢索的粒度，機制和由冷變熱的合并
冷元組的識別 On-line——DBMS會檢測事務(wù)訪問的部分和追蹤元組被訪問的頻率；追蹤信息的元數(shù)據(jù)直接嵌在元組內(nèi)；Off-line——在事務(wù)執(zhí)行時會維護一個元組訪問日志，用后臺進程來計算訪問頻率。
驅(qū)逐時間 閾值——DBMS檢測內(nèi)存的使用情況，當內(nèi)存使用到某個閾值時開始驅(qū)逐元組，但DBSM需要手動的移動數(shù)據(jù)；OS虛擬內(nèi)存——OS決定什么時候把數(shù)據(jù)移入磁盤，后臺進行。
被驅(qū)逐元組的元數(shù)據(jù)（在內(nèi)存還是磁盤，磁盤中的如何訪問） Tombstones——留一個標志指向磁盤中元組的地址，并更新索引中這個元組的指針指向這個Tombstone元組；布隆過濾器——每個索引用相似的數(shù)據(jù)結(jié)構(gòu)，每個查詢都是索引+過濾器進行查找(先用布隆過濾器看在不在，不在直接去磁盤中查找)；OS虛擬內(nèi)存——OS會track哪些數(shù)據(jù)在磁盤，DBMS不需要額外的元數(shù)據(jù)。
數(shù)據(jù)檢索粒度 一塊中的所有元組——無論是否需要都把這一塊中所有元組都合并入In-Memory Table Heap中，會需要很多CPU開銷來更新索引 ，元組也更容易被驅(qū)逐；只合并需要的元組——只把查詢訪問的元組合并到In-memory table heap中，但是需要額外的bookkeeping to track holes
合并閾值 總是合并——檢索的元組統(tǒng)統(tǒng)合并；只合并更新——除更新外的其他的放在臨時緩存中；選擇性更新——追蹤每個塊被訪問的頻率，如果一個塊訪問超過閾值就把這個塊合并入in-memory table heap中。
檢索機制 abort-and-restart——如果一個事務(wù)要訪問被驅(qū)逐的元組就把這個事務(wù)abort，然后一個單獨的后臺線程從磁盤中檢索這個元組合并到內(nèi)存中；數(shù)據(jù)準備好后restart這個事務(wù)，在大量查詢時無法保證一致性； 異步檢索——stall訪問被驅(qū)逐的元組的事務(wù)直到把這個元組從磁盤中取出并合并入內(nèi)存
