倒排索引技術索引器文檔

倒排索引

什麼是倒排索引呢？索引咱們都知道，就是爲了能更快的找到文檔的數據結構，好比給文檔編個號，那麼經過這個號就能夠很快的找到某一篇文檔，而倒排索引不是根據文檔編號，而是經過文檔中的某些個詞而找到文檔的索引結構。緩存

倒排索引技術簡單，高效，簡直是爲搜索引擎這種東西量身定作的，就是靠這個技術，實現一個搜索引擎才成爲可能，咱們也才能在海量的文章中經過一個關鍵詞找到咱們想要的內容。微信

咱們看個例子，有下面的幾個文檔：數據結構

文檔編號 文檔內容
1 這是一個Go語言實現的搜索引擎
2 PHP是世界上最好的語言
3 Linux是C語言和彙編語言實現的
4 谷歌是一個世界上最好的搜索引擎公司 
1,2,3,4

倒排索引【只列出了部分關鍵詞】函數

關鍵詞 文檔編號
Go 1
語言 1，2，3
實現 1，3
搜索引擎 1，4
PHP 2
世界 2，4
最好 2，4
彙編 3
公司 4

這樣就很是好理解了吧，實際上倒排索引就是把文檔的內容切詞之後從新生成了一個表格，經過這個表格，咱們能夠很快的找到每一個關鍵詞對應的文檔，好了，沒有了，到這裏，就是倒排索引的核心原理，也是搜索引擎最基礎的基石，不論是谷歌仍是某度，最核心的東西就是這兩個表格了，呵呵，沒這兩表格，啥都幹不了。性能

搜索引擎

上面就是搜索引擎的最基礎的技術了，若是來設計一個數據結構和算法來實現表2就成了搜索引擎技術的關鍵。this

MMAPMMAP

MMAP系統調用

mmap是將一個文件或者其它對象映射進內存。文件被映射到多個頁上，若是文件的大小不是全部頁的大小之和，最後一個頁不被使用的空間將會清零。實現這樣的映射關係後，進程就能夠採用指針的方式讀寫操做這一段內存，而系統會自動回寫髒頁面到對應的文件磁盤上，即完成了對文件的操做而沒必要再調用read,write等系統調用函數。

mmap最大的一個好處是操做系統會本身將磁盤上的文件映射到內存，當內存足夠的時候，操做文件就像操做內存同樣快，而當內存不足的時候，操做系統又會本身將一些頁從內存中去掉，實現了一個相似緩存的東西。特別適合於對於巨大文件的讀操做，而咱們的倒排索引文件就是這種巨大的文件，並且基本上寫入一次之後就不太修改了，每次查詢都讀操做，因此使用mmap是一個比較好的選擇。

mmap是一個系統調用，不一樣的操做系統實現有所不一樣，Linux下對應的C的調用方法是下面這個，具體的參數含義你們能夠man一下：

頭文件
函數原型
void mmap(void start,size_t length,int prot,int flags,int fd,off_t offset);

一個巨大的文件mmap以後，文件讀寫操做的性能由系統內存決定，系統可用內存越大，那麼讀寫文件的性能越好，由於操做系統的內存足夠，系統會將更多的文件載入到內存，提升系統吞吐量。

Syscall

func Mmap(fd int, offset int64, length int, prot int, flags int) (data []byte, err error)

參數分別是：文件描述符，偏移量，須要映射的長度，指望的內存保護標誌【是隻讀仍是隻寫仍是讀寫】，映射方式【是否同步到文件，仍是隻是副本修改等】。

由於mmap是基礎實現，不少地方都須要使用，因此單獨實現了一個mmap的類，在utils.mmap中，提供一些基礎的方法：

func NewMmap(file_name string, mode int) (Mmap, error) 新建一個mmap
func (this Mmap) ReadInt64(start int64) int64 //從指定位置讀取一個int64的值
func (this Mmap) WriteInt64(start, value int64) error //在指定位置寫入一個int64的值
func (this Mmap) ReadDocIdsArry(start, len uint64) []DocIdNode //從指定位置讀取一個docid的鏈
......

倒排文件
1 1，2，3 1，3 1，4 2 2，4 2，4 3 4

而第一列咱們將保存關鍵字和偏移量。這樣，表2就被咱們拆分紅兩個數據結構了，如今的關鍵是第一列使用什麼數據結構能夠保證在查詢的時候迅速找到對應的關鍵字，從而找到偏移量獲得第二列的具體數據。

順序表哈希表查找樹前綴樹

歡迎你們掃描一下下面的微信公衆號訂閱，首先會在這裏發出來：）