Web Indexing
【簡介】
Web Indexing又稱為Internet Indexing故名思義是一套索引機制，就好像是一本書的索引目錄，可以根據關鍵字來查詢網頁資源，應用領域不限於internet，可延申到Intranet或Desktop Indexing，這樣的技術正是在實作搜尋引擎的索引資料庫，只要把常用的關鍵字搜集整理出來，然後再按照關鍵字去對映網頁地址，以及點閱率排名，再把這些對映結果存放在可以快速搜尋的分散式資料庫中，就可以處理整個全球資訊網的網站索引；關於關鍵字的索引及對映工作，可以使用Map Reduce去做分散式批次處理比對工作，以全球資訊網的資訊量來說都是terabyte的容量起算，所以使用Map Reduce來做定期規律的分散式批次運算較合適，然後再將結果存放到Bigtable/Hypertable/HBase這一類的分散式數據資料庫裡提供查詢程式讀取，這就成了搜尋引擎的索引資料庫。
【搜尋引擎原理說明】
搜尋引擎的基本原理，是先透過爬網頁程式搜集全球資訊網路上所有的網頁資訊後，將這些網頁全部儲存起來，留待接下來的分析處理之用；搜尋引擎供應商透過一些網頁查詢記錄與Data Mining等技術，把常用的搜尋關鍵字找出來並整理成關鍵字資料庫；有了全球資訊網的網頁內容與搜尋關鍵字之後，再結合Map Reduce技術來把內含關鍵字的網頁過濾出來，並且一邊統計網頁內含的關鍵字出現次數及以及點閱率，再把這份結果整理出來建立搜尋關鍵字與網頁對映查詢的索引表格，然後將這份表格存放到像Bigtable/Hypertable/HBase等分散式數據資料庫，接著使用者只要透過瀏覽器就可以發出關鍵字搜尋指令給伺服器端的查詢程式，這支程式只要到資料庫取出查詢結果回傳給瀏覽器，就大功告成了。
備註：關於伺服器端的查詢程式如何處理網路流量的負載平衡，以及分散式資料庫的負載平衡架構如何處理，留待日後再做分析討論。
【索引表格實作流程推導說明】
由於每一家搜尋引擎公司所建立的web indexing機制可能不太一樣，我們採用Google公佈的論文資料加上我們自己的推測之後，歸納出以下的可能作法：
- 原始資料 -> (Map Reduce處理) -> 1個關鍵字詞的索引結果 -> (匯入Hypertable/HBase) -> web indexing table (1keyword)
- web indexing table (1keyword) -> (Map Reduce處理) -> 2個關鍵字詞的索引結果 -> (匯入Hypertable/HBase) -> web indexing table (2keyword)
- web indexing table (2keyword) -> (Map Reduce處理) -> 3個關鍵字詞的索引結果 -> (匯入Hypertable/HBase) -> web indexing table (3keyword)
- 重覆Map Reduce處理，並建立3組以上的關鍵字索引資料表
- Google的查詢上限是32個字詞，不區分大小寫，使用引號括住的字詞會特別依照字詞需要相連在一起來查詢，單一字詞的長度有上限約為128個字母，例如查詢條件"a b"，代表2個字詞，它所對映到的網頁內容可能是a b/ab/a-b或是2個大寫相連的字詞，如：Ancienne Belgique
- 以上的字詞庫，例如:關鍵字a b代表2個字詞，它所對映到的網頁內容可能是a b/ab或是以其他字詞隔開的可能內容
【簡單的範例說明】
- 以下的範例會介紹當關鍵字與網頁內容對映關連整理出來之後，怎麼把這些對映建立到像是hypertable或hbase這種key-value mapping的column-oriented Table當中，透過這樣的資料結構存放方式，在搜尋引擎當中如何發揮功效。
下列這張表格是假設從網路上取得的模擬資料範例，真實的網址與網頁內容應該是較複雜的資料數據，為求簡化說明方式，我們以最簡單的a/b/c/d/e代表不同的關鍵字內容，01.htm-10.htm代表10份不同的網址。
- 虛擬網頁內容說明
| 虛擬網址 | 虛擬網頁內容 |
| 01.htm | a b c d e |
| 02.htm | a b c d |
| 03.htm | a b c |
| 04.htm | a b |
| 05.htm | a |
| 06.htm | b |
| 07.htm | c |
| 08.htm | d |
| 09.htm | e |
| 10.htm | b c |
- 建立資料庫schema
以關鍵字為Rowkey，column family目前只建立一組取名url，虛擬網址就是column qualifier/key，虛擬網頁內容就是value，這樣一來只要查詢關鍵字，就可以立刻找出相關網址及網頁內容。
| Rowkey | Column Family | Column Qualifier | Value |
| 關鍵字 | url(或其他名稱) | 虛擬網址 | 虛擬網頁內容 |
- 建立多組關鍵字對映表
假設經過map reduce的數據處理之後，產生了多組關鍵字的對應關係資料表格，然後根據這份表格再把它匯入到hypertable或hbase當中，當作搜尋引擎的搜尋資料庫。
2.1 建立一組關鍵字對映表
| 關鍵字 | 虛擬網址 | 虛擬網頁內容 |
| a | 01.htm | a b c d e |
| a | 02.htm | a b c d |
| a | 03.htm | a b c |
| a | 04.htm | a b |
| a | 05.htm | a |
| b | 01.htm | a b c d e |
| b | 02.htm | a b c d |
| b | 03.htm | a b c |
| b | 04.htm | a b |
| b | 06.htm | b |
| b | 10.htm | b c |
| c | 01.htm | a b c d e |
| c | 02.htm | a b c d |
| c | 03.htm | a b c |
| c | 07.htm | c |
| c | 10.htm | b c |
| d | 01.htm | a b c d e |
| d | 02.htm | a b c d |
| d | 08.htm | d |
| e | 01.htm | a b c d e |
| e | 09.htm | e |
2.2 建立二組關鍵字對映表
| 關鍵字 | 虛擬網址 | 虛擬網頁內容 |
| a b | 01.htm | a b c d e |
| a b | 02.htm | a b c d |
| a b | 03.htm | a b c |
| a b | 04.htm | a b |
| b c | 01.htm | a b c d e |
| b c | 02.htm | a b c d |
| b c | 03.htm | a b c |
| b c | 10.htm | b c |
【面臨的問題點】
- 應該挑選哪些字詞作為關鍵字，以及當關鍵字詞組數目一多起來的時候，Map Reduce程式的複雜度會隨之增加
- 當應用面鎖定在生物醫學領域的應用時，如何證明其效能優於MySQL的查詢方式，以及大量測試資料如何取得
- 應該選用哪一套效能測試軟體來評估Hypertable/HBase/Mysql較為公平
【應用面】
- 陽明的生物醫學資料庫
- 其他領域應用
