設想一下，互聯網宛如一座龐大的圖書館，而每一個網頁恰似其中的一冊書籍。URL 就如同書籍的標題，磁盤位置則等同于書籍在圖書館書架上的精準定位。如今，我們的使命是根據書籍的標題尋覓其在書架上的位置，進而將其取出。
在現實中的圖書館里，通常都會存在一個數據庫，用以記載書籍以及相應的書架編號，如此一來，憑借書名便能夠知曉其所在位置。這個數據庫便是記錄書名與位置之間的關聯，然而，每次數據庫自磁盤啟動時，這一關聯都需要重新構建，倘若數據量極為龐大，那么重建所需的時間可能會相當漫長，那么是否存在不必建立此類關聯的可能呢？
首先，我們需要為每一本書賦予一個獨一無二的標識符，我們將其稱作“MD5 值”。這恰似我們為每本書貼上了一個獨特的條形碼。
有了書籍的條形碼（MD5 值）之后，試想一下，倘若我們擁有一個大書架，每個格子對應一個 md5，如此一來，給出一個條形碼便能找到對應的格子，但這種情況在現實中難以實現，畢竟哪有如此巨大的書架。
于是，我們采用了一種方法：構建了一個大書架（哈希表），并非每個條形碼都擁有單獨的書架格子。相反，我們將眾多的條形碼映射至同一個格子上。
當兩個不同的條形碼映射到同一個書架格子時，這種情況被稱作“沖突”。為了化解這一難題，我們在每個書架格子上懸掛了若干小籃子（鏈表），所有映射至此格子的書籍都被放置在這些小籃子中。
如此一來，當我們想要找一本書時，依據 md5 值便可找到對應的格子，接著查看格子里的所有小籃子里是否存在我們所需的書籍。
Apache Traffic Server（ATS）便是依照這樣的方式運作。它運用 MD5 值充當條形碼，構建了一個大書架（哈希表），并且在每個格子上懸掛了若干小籃子（鏈表）來應對沖突。
具體實現 ats 索引結構是這樣的
ats 索引大小是固定的，初始化的時候會根據磁盤大小，文件平均大小，一次性創建若干segments，每個segment不超過65535個索引(dir)， 每個segment里包含相同的buckets數量，每個bucket包含4個索引(dir)，并且每個segment有一個freelist鏈表，這個防止每個bucket里面4個索引不夠用解決hash沖突用的，所有segment下bucket共用同一freelist取索引
上圖一個索引結構，這個結構就是固化到磁盤上，相當于磁盤上一個大數組，緩存啟動的時候加載這個大的數組到內存，索引關系自動就有了，包括
VolHeaderFooter,freelist[segments], raw dir, VolHeadFooter
VolHeaderFooter就是索引的元數據，記錄當前寫入的位置，圈數
freelist[segments] 每個segments的freelist，如上圖，初始化的時候會將每個segment所有bucket下的2,3,4索引組成該segment的feelist鏈表
raw dir， 就是索引（dir），每個索引10個字節，每個索引記錄磁盤位置，文件大小等信息
緩存的查找：
根據緩存的url計算出md5值，之后計算segment和bucket，之后遍歷bucket里面索引，找到需要的索引，因為索引的信息沒有記錄md5值，所以找到的索引不一定是要的索引，需要讀取磁盤信息，因為磁盤數據里是記錄md5值的
ats 索引優點：
1.索引只有10個字節，支持TB級別的數據，也不過就G級別內存，例如7TB盤，平均存儲大小64KB，每個索引10個字節， 需要 1GB內存
2. 不用啟動的時候重新建立索引，給一個url，就可以算出md5值，之后就可以計算出segment bucket
缺點
1. 浪費索引，大多數索引是用不到的，可以看到索引也就用了20%
2. 索引不能準確知道是否要找的，需要讀取磁盤才能知道，這樣讀取磁盤就限制其相關性能了
