PHP實現文本快速查找-二分查找法

起因

先說說事情的起因，最近在分析數據時經常遇到一種場景，代碼需要頻繁的讀某一張資料庫的表，比如根據地區ID獲取地區名稱、根據網站分類ID獲取分類名稱、根據關鍵詞ID獲取關鍵詞等。雖然以上需求都可以在原始建表時，通過冗餘數據來解決。但仍有部分業務存的只是關聯表的ID，數據分析時需要頻繁的查表。

所讀的表存在共同的特點

數據幾乎不會變更

數據量適中，從一萬到100多萬，如果全載入到內存也不太合適。

糾結的地方

在做數據分析時，需要十分頻繁的讀這些表，每秒有可能需要讀上萬次。其實內部的資料庫集群完全可以勝任，但會對線上業務稍有影響。（你懂得，小公司不可能為離線分析做一套完整的數據存儲服務。大部分數據分析還要藉助線上的數據集群）

優化方案的思考

有沒有一種方式可以不增加線上的壓力，同時提供更高效的查詢方式？想過redis，但最終選擇用文本存儲。因為數據分析是一個獨立的需求，不希望與現有的redis集群或者其它存儲服務有交集。還有一個原因是每次分析的中間結果，對下一次分析並沒有很大的實質作用，並不需要把結果持久存儲，而且占的內存也會較多。最終使用文本存儲，然後用二分來查找。特點，1，存儲非常快，雖然redis等nosql服務雖然已經非常快，但仍無法與文本存儲相提並論；2，查找的時候使用二分查找，百萬條記錄查詢也可在0.1ms內完成（使用線上的普通硬碟，如果是ssd盤會更快）。

實現步驟

將資料庫中需要的欄位導出到文本

將導出的文本（已經按id進行過排序）轉換格式重新存儲

程序讀取轉換後的格式

文本存儲格式

說明 ：需求中，文本每行有兩列，第一列是主建ID（數字），第二列為文本。整個文本已經按第一列有序排列，兩列之間用tab鍵分隔。 之前有看過ip.dat的存儲，本次仿照其存儲格式：將文本中的內容每行轉換為固定長度後，存儲到新的文件。搜索時，使用文件操作函數fopen，fseek，fgets等函數按位元組讀取內容，並以二分查找法快速定位需要的內容。

代碼實現部分

通用類，類似需求只需要提供符合標準的文本（每行兩列，第一列為查找的ID，第二列為文本。同時文本已經按第一列有序排序）

生成以上所提到的存儲格式

提供根據id查詢介面

代碼片斷

點擊展開全文

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！