索引演算法

Ⅰ 索引方式定址演算法的介紹

王同學 作業要自己做！

Ⅱ 談談資料庫索引 用自己話說

資料庫原索引不僅表現在排序和查找上,更主要的是通過建立合適的索引,還可以防止關鍵字重復!建立索引的資料庫和沒有建立索引的資料庫在查找速度上,不是一倍兩倍的問題,而是幾何級倍的問題!所以,不管是什麼資料庫,至少要建立一個索引.很簡的道理,你要在網上搜一個主題,如果你要搜的主題在資料庫中不是索引欄位,那查找是非常耗時的.但如果你有建立相應的索引,那結果就是天壤之別!

Ⅲ 搜索引擎中索引時怎麼實現的

隨著互聯網的迅猛發展、WEB信息的增加，用戶要在信息海洋里查找自己所需的信息，就象大海撈針一樣，搜索引擎技術恰好解決了這一難題（它可以為用戶提供信息檢索服務）。搜索引擎是指互聯網上專門提供檢索服務的一類網站，這些站點的伺服器通過網路搜索軟體(例如網路搜索機器人)或網路登錄等方式，將Intemet上大量網站的頁面信息收集到本地，經過加工處理建立信息資料庫和索引資料庫，從而對用戶提出的各種檢索作出響應，提供用戶所需的信息或相關指針。用戶的檢索途徑主要包括自由詞全文檢索、關鍵詞檢索、分類檢索及其他特殊信息的檢索(如企業、人名、電話黃頁等)。下面以網路搜索機器人為例來說明搜索引擎技術。
1．網路機器人技術
網路機器人(Robot)又被稱作Spider、Worm或Random，核心目的是為獲取Intemet上的信息。一般定義為「一個在網路上檢索文件且自動跟蹤該文件的超文本結構並循環檢索被參照的所有文件的軟體」。機器人利用主頁中的超文本鏈接遍歷WWW，通過U趾引用從一個HT2LIL文檔爬行到另一個HTML文檔。網上機器人收集到的信息可有多種用途，如建立索引、HIML文件合法性的驗證、uRL鏈接點驗證與確認、監控與獲取更新信息、站點鏡像等。
機器人安在網上爬行，因此需要建立一個URL列表來記錄訪問的軌跡。它使用超文本，指向其他文檔的URL是隱藏在文檔中，需要從中分析提取URL，機器人一般都用於生成索引資料庫。所有WWW的搜索程序都有如下的工作步驟：
(1)機器人從起始URL列表中取出URL並從網上讀取其指向的內容；
(2)從每一個文檔中提取某些信息(如關鍵字)並放入索引資料庫中；
(3)從文檔中提取指向其他文檔的URL，並加入到URL列表中；
(4)重復上述3個步驟，直到再沒有新的URL出現或超出了某些限制(時間或磁碟空間)；
(5)給索引資料庫加上檢索介面，向網上用戶發布或提供給用戶檢索。
搜索演算法一般有深度優先和廣度優先兩種基本的搜索策略。機器人以URL列表存取的方式決定搜索策略：先進先出，則形成廣度優先搜索，當起始列表包含有大量的WWW伺服器地址時，廣度優先搜索將產生一個很好的初始結果，但很難深入到伺服器中去；先進後出，則形成深度優先搜索，這樣能產生較好的文檔分布，更容易發現文檔的結構，即找到最大數目的交叉引用。也可以採用遍歷搜索的方法，就是直接將32位的IP地址變化，逐個搜索整個Intemet。
搜索引擎是一個技術含量很高的網路應用系統。它包括網路技術、資料庫技術動標引技術、檢索技術、自動分類技術，機器學習等人工智慧技術。
2．索引技術
索引技術是搜索引擎的核心技術之一。搜索引擎要對所收集到的信息進行整理、分類、索引以產生索引庫，而中文搜索引擎的核心是分詞技術。分詞技術是利用一定的規則和詞庫，切分出一個句子中的詞，為自動索引做好准備。目前的索引多採用Non—clustered方法，該技術和語言文字的學問有很大的關系，具體有如下幾點：
(1)存儲語法庫，和詞彙庫配合分出句子中的詞彙；
(2)存儲詞彙庫，要同時存儲詞彙的使用頻率和常見搭配方式；
(3)詞彙寬，應可劃分為不同的專業庫，以便於處理專業文獻；
(4)對無法分詞的句子，把每個字當作詞來處理。
索引器生成從關鍵詞到URL的關系索引表。索引表一般使用某種形式的倒排表(1nversionUst)，即由索引項查找相應的URL。索引表也要記錄索引項在文檔中出現的位置，以便檢索器計算索引項之間的相鄰關系或接近關系，並以特定的數據結構存儲在硬碟上。
不同的搜索引擎系統可能採用不盡相同的標引方法。例如Webcrawler利用全文檢索技術，對網頁中每一個單詞進行索引；Lycos只對頁名、標題以及最重要的100個注釋詞等選擇性詞語進行索引；Infoseek則提供概念檢索和片語檢索，支持and、or、near、not等布爾運算。檢索引擎的索引方法大致可分為自動索引、手工索引和用戶登錄三類。
3. 檢索器與結果處理技術
檢索器的主要功能是根據用戶輸入的關鍵詞在索引器形成的倒排表中進行檢索，同時完成頁面與檢索之間的相關度評價，對將要輸出的結果進行排序，並實現某種用戶相關性反饋機制。
通過搜索引擎獲得的檢索結果往往成百上千，為了得到有用的信息，常用的方法是按網頁的重要性或相關性給網頁評級，進行相關性排序。這里的相關度是指搜索關鍵字在文檔中出現的額度。當額度越高時，則認為該文檔的相關程度越高。能見度也是常用的衡量標准之一。一個網頁的能見度是指該網頁入口超級鏈接的數目。能見度方法是基於這樣的觀點：一個網頁被其他網頁引用得越多，則該網頁就越有價值。特別地，一個網頁被越重要的網頁所引用，則該網頁的重要程度也就越高。結果處理技術可歸納為：
(1)按頻次排定次序 通常，如果一個頁麵包含了越多的關鍵詞，其搜索目標的相關性應該越好，這是非常合平常理的解決方案。
(2)按頁面被訪問度排序 在這種方法中，搜索引擎會記錄它所搜索到的頁面被訪問的頻率。人們訪問較多的頁面通常應該包含比較多的信息，或者有其他吸引入的長處。這種解決方案適合一般的搜索用戶，而因為大部分的搜索引擎都不是專業性用戶，所以這種方案也比較適合一般搜索引擎使用。
(3)二次檢索 進一步凈化(比flne)結果，按照一定的條件對搜索結果進行優化，可以再選擇類別、相關詞進行二次搜索等。
由於目前的搜索引擎還不具備智能，除非知道要查找的文檔的標題，否則排列第一的結果未必是「最好」的結果。所以有些文檔盡管相關程度高，但並不一定是用戶最需要的文檔。
搜索引擎技術的行業應用：
搜索引擎的行業應用一般指類似於千瓦通信提供的多種搜索引擎行業與產品應用模式，大體上分為如下幾種形式：
1、 政府機關行業應用
n 實時跟蹤、採集與業務工作相關的信息來源。
n 全面滿足內部工作人員對互聯網信息的全局觀測需求。
n 及時解決政務外網、政務內網的信息源問題，實現動態發布。
n 快速解決政府主網站對各地級子網站的信息獲取需求。
n 全面整合信息，實現政府內部跨地區、跨部門的信息資源共享與有效溝通。
n 節約信息採集的人力、物力、時間，提高辦公效率。
2、企業行業應用
n 實時准確地監控、追蹤競爭對手動態，是企業獲取競爭情報的利器。
n 及時獲取競爭對手的公開信息以便研究同行業的發展與市場需求。
n 為企業決策部門和管理層提供便捷、多途徑的企業戰略決策工具。
n 大幅度地提高企業獲取、利用情報的效率，節省情報信息收集、存儲、挖掘的相關費用，是提高企業核心競爭力的關鍵。
n 提高企業整體分析研究能力、市場快速反應能力，建立起以知識管理為核心的競爭情報數據倉庫，是提高企業核心競爭力的神經中樞。
3、新聞媒體行業應用
n 快速准確地自動跟蹤、採集數千家網路媒體信息，擴大新聞線索，提高採集速度。
n 支持每天對數萬條新聞進行有效抓取。監控范圍的深度、廣度可以自行設定。
n 支持對所需內容智能提取、審核。
n 實現互聯網信息內容採集、瀏覽、編輯、管理、發布的一體化。
4、 行業網站應用
n 實時跟蹤、採集與網站相關的信息來源。
n 及時跟蹤行業的信息來源網站，自動，快速更新網站信息。動態更新信息。
n 實現互聯網信息內容採集、瀏覽、編輯、管理、發布的一體化。
n 針對商務網站提出商務管理模式，大大提高行業網站的商務應用需求。
n 針對資訊網站分類目錄生成，提出用戶生成網站分類結構。並可以實時增加與更新分類結構。不受級數限制。從而大大利高行業的應用性。
n 提供搜索引擎SEO優化專業服務，快速提高行業網站的推廣。
n 提供與CCDC呼叫搜索引擎的廣告合作。建立行業網站聯盟，提高行業網站知名度。
5) 網路信息監察與監控
n 網路輿情系統。如「千瓦通信-網路輿情雷達監測系統」
n 網站信息與內容監察與監控系統，如「千瓦通信-網站信息與內容監測與監察系統（站內神探）」
隨著網際網路的迅猛發展、WEB信息的增加，用戶要在信息海洋里查找信息，就象大海撈
針一樣，搜索引擎技術恰好解決了這一難題（它可以為用戶提供信息檢索服務）。目前，
搜索引擎技術正成為計算機工業界和學術界爭相研究、開發的對象。
搜索引擎（Search Engine）是隨著WEB信息的迅速增加，從1995年開始逐漸發展起來
的技術。據發表在《科學》雜志1999年7月的文章《WEB信息的可訪問性》估計，全球目前
的網頁超過8億，有效數據超過9T，並且仍以每4個月翻一番的速度增長。用戶要在如此浩
瀚的信息海洋里尋找信息，必然會"大海撈針"無功而返。搜索引擎正是為了解決這個"迷航
"問題而出現的技術。搜索引擎以一定的策略在互聯網中搜集、發現信息，對信息進行理解
、提取、組織和處理，並為用戶提供檢索服務，從而起到信息導航的目的。搜索引擎提供
的導航服務已經成為互聯網上非常重要的網路服務，搜索引擎站點也被美譽為"網路門戶"
。搜索引擎技術因而成為計算機工業界和學術界爭相研究、開發的對象。本文旨在對搜索
引擎的關鍵技術進行簡單的介紹，以起到拋磚引玉的作用。

分 類

按照信息搜集方法和服務提供方式的不同，搜索引擎系統可以分為三大類：
1．目錄式搜索引擎：以人工方式或半自動方式搜集信息，由編輯員查看信息之後，人
工形成信息摘要，並將信息置於事先確定的分類框架中。信息大多面向網站，提供目錄瀏
覽服務和直接檢索服務。該類搜索引擎因為加入了人的智能，所以信息准確、導航質量高
，缺點是需要人工介入、維護量大、信息量少、信息更新不及時。這類搜索引擎的代表是
：Yahoo、LookSmart、Open Directory、Go Guide等。
2．機器人搜索引擎：由一個稱為蜘蛛（Spider）的機器人程序以某種策略自動地在互
聯網中搜集和發現信息，由索引器為搜集到的信息建立索引，由檢索器根據用戶的查詢輸
入檢索索引庫，並將查詢結果返回給用戶。服務方式是面向網頁的全文檢索服務。該類搜
索引擎的優點是信息量大、更新及時、毋需人工干預，缺點是返回信息過多，有很多無關
信息，用戶必須從結果中進行篩選。這類搜索引擎的代表是：AltaVista、Northern Ligh
t、Excite、Infoseek、Inktomi、FAST、Lycos、Google；國內代表為："天網"、悠遊、O
penFind等。
3．元搜索引擎：這類搜索引擎沒有自己的數據，而是將用戶的查詢請求同時向多個搜
索引擎遞交，將返回的結果進行重復排除、重新排序等處理後，作為自己的結果返回給用
戶。服務方式為面向網頁的全文檢索。這類搜索引擎的優點是返回結果的信息量更大、更
全，缺點是不能夠充分使用所使用搜索引擎的功能，用戶需要做更多的篩選。這類搜索引
擎的代表是WebCrawler、InfoMarket等。

性 能 指 標
我們可以將WEB信息的搜索看作一個信息檢索問題，即在由WEB網頁組成的文檔庫中檢索
出與用戶查詢相關的文檔。所以我們可以用衡量傳統信息檢索系統的性能參數-召回率（R
ecall）和精度（Pricision）衡量一個搜索引擎的性能。
召回率是檢索出的相關文檔數和文檔庫中所有的相關文檔數的比率，衡量的是檢索系
統（搜索引擎）的查全率；精度是檢索出的相關文檔數與檢索出的文檔總數的比率，衡量
的是檢索系統（搜索引擎）的查准率。對於一個檢索系統來講，召回率和精度不可能兩全
其美：召回率高時，精度低，精度高時，召回率低。所以常常用11種召回率下11種精度的
平均值（即11點平均精度）來衡量一個檢索系統的精度。對於搜索引擎系統來講，因為沒
有一個搜索引擎系統能夠搜集到所有的WEB網頁，所以召回率很難計算。目前的搜索引擎系
統都非常關心精度。
影響一個搜索引擎系統的性能有很多因素，最主要的是信息檢索模型，包括文檔和查詢
的表示方法、評價文檔和用戶查詢相關性的匹配策略、查詢結果的排序方法和用戶進行相
關度反饋的機制。

主 要 技 術
一個搜索引擎由搜索器、索引器、檢索器和用戶介面等四個部分組成。
1.搜索器
搜索器的功能是在互聯網中漫遊，發現和搜集信息。它常常是一個計算機程序，日夜
不停地運行。它要盡可能多、盡可能快地搜集各種類型的新信息，同時因為互聯網上的信
息更新很快，所以還要定期更新已經搜集過的舊信息，以避免死連接和無效連接。目前有
兩種搜集信息的策略：
● 從一個起始URL集合開始，順著這些URL中的超鏈（Hyperlink），以寬度優先、深
度優先或啟發式方式循環地在互聯網中發現信息。這些起始URL可以是任意的URL，但常常
是一些非常流行、包含很多鏈接的站點（如Yahoo！）。
● 將Web空間按照域名、IP地址或國家域名劃分，每個搜索器負責一個子空間的窮盡
搜索。 搜索器搜集的信息類型多種多樣，包括HTML、XML、Newsgroup文章、FTP文件、
字處理文檔、多媒體信息。 搜索器的實現常常用分布式、並行計算技術，以提高信息
發現和更新的速度。商業搜索引擎的信息發現可以達到每天幾百萬網頁。
2.索引器
索引器的功能是理解搜索器所搜索的信息，從中抽取出索引項，用於表示文檔以及生
成文檔庫的索引表。
索引項有客觀索引項和內容索引項兩種：客觀項與文檔的語意內容無關，如作者名、
URL、更新時間、編碼、長度、鏈接流行度（Link Popularity）等等；內容索引項是用來
反映文檔內容的，如關鍵詞及其權重、短語、單字等等。內容索引項可以分為單索引項和
多索引項（或稱短語索引項）兩種。單索引項對於英文來講是英語單詞，比較容易提取，
因為單詞之間有天然的分隔符（空格）；對於中文等連續書寫的語言，必須進行詞語的切
分。 在搜索引擎中，一般要給單索引項賦與一個權值，以表示該索引項對文檔的區分
度，同時用來計算查詢結果的相關度。使用的方法一般有統計法、資訊理論法和概率法。短
語索引項的提取方法有統計法、概率法和語言學法。
索引表一般使用某種形式的倒排表（Inversion List），即由索引項查找相應的文檔
。索引表也可能要記錄索引項在文檔中出現的位置，以便檢索器計算索引項之間的相鄰或
接近關系（proximity）。
索引器可以使用集中式索引演算法或分布式索引演算法。當數據量很大時，必須實現即時
索引（Instant Indexing），否則不能夠跟上信息量急劇增加的速度。索引演算法對索引器
的性能（如大規模峰值查詢時的響應速度）有很大的影響。一個搜索引擎的有效性在很大
程度上取決於索引的質量。
3.檢索器 檢索器的功能是根據用戶的查詢在索引庫中快速檢出文檔，進行文檔與
查詢的相關度評價，對將要輸出的結果進行排序，並實現某種用戶相關性反饋機制。
檢索器常用的信息檢索模型有集合理論模型、代數模型、概率模型和混合模型四種。
4.用戶介面
用戶介面的作用是輸入用戶查詢、顯示查詢結果、提供用戶相關性反饋機制。主要的
目的是方便用戶使用搜索引擎，高效率、多方式地從搜索引擎中得到有效、及時的信息。
用戶介面的設計和實現使用人機交互的理論和方法，以充分適應人類的思維習慣。
用戶輸入介面可以分為簡單介面和復雜介面兩種。
簡單介面只提供用戶輸入查詢串的文本框；復雜介面可以讓用戶對查詢進行限制，如
邏輯運算（與、或、非；+、-）、相近關系（相鄰、NEAR）、域名范圍（如.e、.com）
、出現位置（如標題、內容）、信息時間、長度等等。目前一些公司和機構正在考慮制定
查詢選項的標准。

未 來 動 向
搜索引擎已成為一個新的研究、開發領域。因為它要用到信息檢索、人工智慧、計算
機網路、分布式處理、資料庫、數據挖掘、數字圖書館、自然語言處理等多領域的理論和
技術，所以具有綜合性和挑戰性。又由於搜索引擎有大量的用戶，有很好的經濟價值，所
以引起了世界各國計算機科學界和信息產業界的高度關注，目前的研究、開發十分活躍，
並出現了很多值得注意的動向。
1.十分注意提高信息查詢結果的精度，提高檢索的有效性 用戶在搜索引擎上進行
信息查詢時，並不十分關注返回結果的多少，而是看結果是否和自己的需求吻合。對於一
個查詢，傳統的搜索引擎動輒返回幾十萬、幾百萬篇文檔，用戶不得不在結果中篩選。解
決查詢結果過多的現象目前出現了幾種方法：一是通過各種方法獲得用戶沒有在查詢語句
中表達出來的真正用途，包括使用智能代理跟蹤用戶檢索行為，分析用戶模型；使用相關
度反饋機制，使用戶告訴搜索引擎哪些文檔和自己的需求相關（及其相關的程度），哪些
不相關，通過多次交互逐步求精。二是用正文分類（Text Categorization）技術將結果分
類，使用可視化技術顯示分類結構，用戶可以只瀏覽自己感興趣的類別。三是進行站點類
聚或內容類聚，減少信息的總量。
2.基於智能代理的信息過濾和個性化服務
信息智能代理是另外一種利用互聯網信息的機制。它使用自動獲得的領域模型（如We
b知識、信息處理、與用戶興趣相關的信息資源、領域組織結構）、用戶模型（如用戶背景
、興趣、行為、風格）知識進行信息搜集、索引、過濾（包括興趣過濾和不良信息過濾）
，並自動地將用戶感興趣的、對用戶有用的信息提交給用戶。智能代理具有不斷學習、適
應信息和用戶興趣動態變化的能力，從而提供個性化的服務。智能代理可以在用戶端進行
，也可以在伺服器端運行。
3.採用分布式體系結構提高系統規模和性能
搜索引擎的實現可以採用集中式體系結構和分布式體系結構，兩種方法各有千秋。但
當系統規模到達一定程度（如網頁數達到億級）時，必然要採用某種分布式方法，以提高
系統性能。搜索引擎的各個組成部分，除了用戶介面之外，都可以進行分布：搜索器可以
在多台機器上相互合作、相互分工進行信息發現，以提高信息發現和更新速度；索引器可
以將索引分布在不同的機器上，以減小索引對機器的要求；檢索器可以在不同的機器上.

Ⅳ 如何寫索引，讓查詢速度快

首先來看看錶是否有索引的命令
show index from 表名；
看到主鍵索引，索引類型是BTREE(二叉樹)
正是因為這個二叉樹演算法，讓查詢速度快很多，二叉樹的原理，就是取最中間的一個數，然後把大於這個數的往右邊排，小於這個數的就向左排，每次減半，然後依次類推，每次減半，形成一個樹狀結構圖
例如上面的例子，我們不使用索引的話，需要查詢11次才把編號為4的數據取出，如果加上索引，我們只需要4次就可以取出。

如大家所知道的，MySQL目前主要有以下幾種索引類型：FULLTEXT，HASH，BTREE，RTREE。
那麼，這幾種索引有什麼功能和性能上的不同呢？
FULLTEXT
即為全文索引，目前只有MyISAM引擎支持。其可以在CREATE TABLE ，ALTER TABLE ，CREATE INDEX 使用，不過目前只有 CHAR、VARCHAR ，TEXT 列上可以創建全文索引。值得一提的是，在數據量較大時候，現將數據放入一個沒有全局索引的表中，然後再用CREATE INDEX創建FULLTEXT索引，要比先為一張表建立FULLTEXT然後再將數據寫入的速度快很多。
全文索引並不是和MyISAM一起誕生的，它的出現是為了解決WHERE name LIKE 「%word%"這類針對文本的模糊查詢效率較低的問題。在沒有全文索引之前，這樣一個查詢語句是要進行遍歷數據表操作的，可見，在數據量較大時是極其的耗時的，如果沒有非同步IO處理，進程將被挾持，很浪費時間，當然這里不對非同步IO作進一步講解，想了解的童鞋，自行谷哥。
全文索引的使用方法並不復雜：
創建ALTER TABLE table ADD INDEX `FULLINDEX` USING FULLTEXT(`cname1`[,cname2…]);
使用SELECT * FROM table WHERE MATCH(cname1[,cname2…]) AGAINST ('word' MODE );
其中， MODE為搜尋方式（IN BOOLEAN MODE ，IN NATURAL LANGUAGE MODE ，IN NATURAL LANGUAGE MODE WITH QUERY EXPANSION / WITH QUERY EXPANSION）。
關於這三種搜尋方式，愚安在這里也不多做交代，簡單地說，就是，布爾模式，允許word里含一些特殊字元用於標記一些具體的要求，如+表示一定要有，-表示一定沒有，*表示通用匹配符，是不是想起了正則，類似吧；自然語言模式，就是簡單的單詞匹配；含表達式的自然語言模式，就是先用自然語言模式處理，對返回的結果，再進行表達式匹配。
對搜索引擎稍微有點了解的同學，肯定知道分詞這個概念，FULLTEXT索引也是按照分詞原理建立索引的。西文中，大部分為字母文字，分詞可以很方便的按照空格進行分割。但很明顯，中文不能按照這種方式進行分詞。那又怎麼辦呢？這個向大家介紹一個Mysql的中文分詞插件Mysqlcft，有了它，就可以對中文進行分詞，想了解的同學請移步Mysqlcft，當然還有其他的分詞插件可以使用。
HASH
Hash這個詞，可以說，自打我們開始碼的那一天起，就開始不停地見到和使用到了。其實，hash就是一種（key=>value）形式的鍵值對，如數學中的函數映射，允許多個key對應相同的value，但不允許一個key對應多個value。正是由於這個特性，hash很適合做索引，為某一列或幾列建立hash索引，就會利用這一列或幾列的值通過一定的演算法計算出一個hash值，對應一行或幾行數據（這里在概念上和函數映射有區別，不要混淆）。在Java語言中，每個類都有自己的hashcode()方法，沒有顯示定義的都繼承自object類，該方法使得每一個對象都是唯一的，在進行對象間equal比較，和序列化傳輸中起到了很重要的作用。hash的生成方法有很多種，足可以保證hash碼的唯一性，例如在MongoDB中，每一個document都有系統為其生成的唯一的objectID（包含時間戳，主機散列值，進程PID，和自增ID）也是一種hash的表現。額，我好像扯遠了-_-!
由於hash索引可以一次定位，不需要像樹形索引那樣逐層查找,因此具有極高的效率。那為什麼還需要其他的樹形索引呢？
在這里愚安就不自己總結了。引用下園子里其他大神的文章：來自 14的路 的MySQL的btree索引和hash索引的區別
（1）Hash 索引僅僅能滿足"=","IN"和"<=>"查詢，不能使用范圍查詢。
由於 Hash 索引比較的是進行 Hash 運算之後的 Hash 值，所以它只能用於等值的過濾，不能用於基於范圍的過濾，因為經過相應的 Hash 演算法處理之後的 Hash 值的大小關系，並不能保證和Hash運算前完全一樣。
（2）Hash 索引無法被用來避免數據的排序操作。
由於 Hash 索引中存放的是經過 Hash 計算之後的 Hash 值，而且Hash值的大小關系並不一定和 Hash 運算前的鍵值完全一樣，所以資料庫無法利用索引的數據來避免任何排序運算；
（3）Hash 索引不能利用部分索引鍵查詢。
對於組合索引，Hash 索引在計算 Hash 值的時候是組合索引鍵合並後再一起計算 Hash 值，而不是單獨計算 Hash 值，所以通過組合索引的前面一個或幾個索引鍵進行查詢的時候，Hash 索引也無法被利用。
（4）Hash 索引在任何時候都不能避免表掃描。
前面已經知道，Hash 索引是將索引鍵通過 Hash 運算之後，將 Hash運算結果的 Hash 值和所對應的行指針信息存放於一個 Hash 表中，由於不同索引鍵存在相同 Hash 值，所以即使取滿足某個 Hash 鍵值的數據的記錄條數，也無法從 Hash 索引中直接完成查詢，還是要通過訪問表中的實際數據進行相應的比較，並得到相應的結果。
（5）Hash 索引遇到大量Hash值相等的情況後性能並不一定就會比B-Tree索引高。
對於選擇性比較低的索引鍵，如果創建 Hash 索引，那麼將會存在大量記錄指針信息存於同一個 Hash 值相關聯。這樣要定位某一條記錄時就會非常麻煩，會浪費多次表數據的訪問，而造成整體性能低下。

愚安我稍作補充，講一下HASH索引的過程，順便解釋下上面的第4,5條：
當我們為某一列或某幾列建立hash索引時（目前就只有MEMORY引擎顯式地支持這種索引），會在硬碟上生成類似如下的文件：
hash值 存儲地址
1db54bc745a1 77#45b5
4bca452157d4 76#4556,77#45cc…
…
hash值即為通過特定演算法由指定列數據計算出來，磁碟地址即為所在數據行存儲在硬碟上的地址（也有可能是其他存儲地址，其實MEMORY會將hash表導入內存）。
這樣，當我們進行WHERE age = 18 時，會將18通過相同的演算法計算出一個hash值==>在hash表中找到對應的儲存地址==>根據存儲地址取得數據。
所以，每次查詢時都要遍歷hash表，直到找到對應的hash值，如（4），數據量大了之後，hash表也會變得龐大起來，性能下降，遍歷耗時增加，如（5）。
BTREE
BTREE索引就是一種將索引值按一定的演算法，存入一個樹形的數據結構中，相信學過數據結構的童鞋都對當初學習二叉樹這種數據結構的經歷記憶猶新，反正愚安我當時為了軟考可是被這玩意兒好好地折騰了一番，不過那次考試好像沒怎麼考這個。如二叉樹一樣，每次查詢都是從樹的入口root開始，依次遍歷node，獲取leaf。
BTREE在MyISAM里的形式和Innodb稍有不同
在 Innodb里，有兩種形態：一是primary key形態，其leaf node里存放的是數據，而且不僅存放了索引鍵的數據，還存放了其他欄位的數據。二是secondary index，其leaf node和普通的BTREE差不多，只是還存放了指向主鍵的信息.
而在MyISAM里，主鍵和其他的並沒有太大區別。不過和Innodb不太一樣的地方是在MyISAM里，leaf node里存放的不是主鍵的信息，而是指向數據文件里的對應數據行的信息.
RTREE
RTREE在mysql很少使用，僅支持geometry數據類型，支持該類型的存儲引擎只有MyISAM、BDb、InnoDb、NDb、Archive幾種。
相對於BTREE，RTREE的優勢在於范圍查找.
各種索引的使用情況
（1）對於BTREE這種Mysql默認的索引類型，具有普遍的適用性
（2）由於FULLTEXT對中文支持不是很好，在沒有插件的情況下，最好不要使用。其實，一些小的博客應用，只需要在數據採集時，為其建立關鍵字列表，通過關鍵字索引，也是一個不錯的方法，至少愚安我是經常這么做的。
（3）對於一些搜索引擎級別的應用來說，FULLTEXT同樣不是一個好的處理方法，Mysql的全文索引建立的文件還是比較大的，而且效率不是很高，即便是使用了中文分詞插件，對中文分詞支持也只是一般。真要碰到這種問題，Apache的Lucene或許是你的選擇。
（4）正是因為hash表在處理較小數據量時具有無可比擬的素的優勢，所以hash索引很適合做緩存（內存資料庫）。如mysql資料庫的內存版本Memsql，使用量很廣泛的緩存工具Mencached，NoSql資料庫redis等，都使用了hash索引這種形式。當然，不想學習這些東西的話Mysql的MEMORY引擎也是可以滿足這種需求的。

Ⅳ 索引順序查找演算法

索引查找是在索引表和主表(即線性表的索引存儲結構)上進行的查找。索引查找的過程是：首先根據給定的索引值K1，在索引表上查找出索引值等於KI的索引項，以確定對應予表在主表中的開始位置和長度，然後再根據給定的關鍵字K2，茬對應的子表中查找出關鍵字等於K2的元素(結點)。對索引表或子表進行查找時，若表是順序存儲的有序表，則既可進行順序查找，也可進行二分查找，否則只能進行順序查找。
設數組A是具有mainlist類型的一個主表，數組B是具有inde)dist類型的在主表A 上建立的一個索引表，m為索引表B的實際長度，即所含的索引項的個數，KI和K2分別為給定待查找的索引值和關鍵字(當然它們的類型應分別為索引表中索引值域的類型和主表中關鍵字域在索引存儲中，不僅便於查找單個元素，而且更便於查找一個子表中的全部元素。當需要對一個子袁中的全部元素依次處理時，只要從索引表中查找出該子表的開始位置即可。由此開始位置可以依次取出該子表中的每一個元素，所以整個查找過程的時間復雜度為，若不是採用索引存儲，而是採用順序存儲，即使把它組織成有序表而進行二分查找時，索引查找一個子表中的所有元素與二分查找一個子表中的所有元素相比。
若在主表中的每個子表後都預留有空閑位置，則索引存儲也便於進行插入和刪除運算，因為其運算過程只涉及到索引表和相應的子表，只需要對相應子表中的元素進行比較和移動，與其它任何子表無關，不像順序表那樣需涉及到整個表中的所有元素，即牽一發而動全身。
在線性表的索引存儲結構上進行插入和刪除運算的演算法，也同查找演算法類似，其過程為：首先根據待插入或刪除元素的某個域(假定子表就是按照此域的值劃分的)的值查找索引表，確定出對應的子表，然後再根據待插入或刪除元素的關鍵字，在該子表中做插入或刪除元素的操作。因為每個子表不是順序存儲，就是鏈接存儲，所以對它們做插入或刪除操作都是很簡單的。

不知道答案與兄台的問題是否一致，也是網上找的，不對請見諒哈~~

Ⅵ 圖書館圖書索引過程中用到的的演算法

圖書索書號一般包括兩個部分（多數情況下佔2行），一是分類號，二是區分號。分類號表示這本書屬於哪一學科類別，區分號表示本圖書館該類圖書的不同品種區分。比如一圖書館買了很多種「C語言編程」的圖書，有張三編的，有李四編的。

Ⅶ 索引的原理

索引是一種利用某種規則的數據結構與實際數據的關系加快數據查找的功能;索引數據節點中有著實際文件的位置,因為索引是根據特定的規則和演算法構建的,在查找的時候遵循索引的規則可以快速查找到對應數據的節點,從而達到快速查找數據的效果。

Ⅷ 演算法與數據結構 索引查找的實現

二分查找法、哈希查找法、二叉排序樹查找法等各種查找演算法。1. 線性表上的查找： 主要分為三種線性結構：順序表，有序順序表，索引順序表。對於第一種，我們採用傳統查找方法，逐個比較。對於及有序順序表我們採用二分查找法。對於第三種索引結構，我們採用索引查找演算法。其中，二分查找還要特別注意適用條件以及其遞歸實現方法。 2.樹表上的查找： 樹表主要分為以下幾種：二叉排序樹，平衡二叉樹，B樹，鍵樹。由於二叉排序樹與平衡二叉樹是一種特殊的二叉樹，所以與二叉樹的聯系就更為緊密。 二叉排序樹，它的中序遍歷結果是一個遞增的有序序列。平衡二叉樹是二叉排序樹的優化，其本質也是一種二叉排序樹，只不過，平衡二叉樹對左右子樹的深度有了限定。 B樹是二叉排序樹的進一步改進，也可以把B樹理解為三叉、四叉....排序樹。因為這兩種演算法涉及到B樹結點的分裂和合並，是一個難點。鍵樹也稱字元樹，特別適用於查找英文單詞的場合。一般不要求能完整描述演算法源碼，多是根據演算法思想建立鍵樹及描述其大致查找過程。 3.基本哈希表的查找演算法： 哈希表查找的基本思想是：根據當前待查找數據的特徵，以記錄關鍵字為自變數，設計一個function，該函數對關鍵字進行轉換後，其解釋結果為待查的地址。堆排序屬於選擇排序類型的排序，是一樹形選擇排序。堆排序的時間，主要由建立初始堆和反復重建堆這兩部分的時間開銷構成，它們均是通過調用Heapify實現的。 堆排序的最壞時間復雜度為O(nlgn)。堆排序的平均性能較接近於最壞性能。 由於建初始堆所需的比較次數較多，所以堆排序不適宜於記錄數較少的文件。 堆排序是就地排序，輔助空間為O(1)， 它是不穩定的排序方法。堆排序，是利用堆這種數據結構的性質，通過堆元素的刪除、調整等一系列操作將最小數選出放在堆頂。堆排序的特點是：在排序過程中，將R[l..n]看成是一棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系，在當前無序區中選擇關鍵字最大(或最小)的記錄。堆排序利用了大根堆(或小根堆)堆頂記錄的關鍵字最大(或最小)這一特徵，使得在當前無序區中選取最大(或最小)關鍵字的記錄變得簡單。
vae.la

Ⅸ 由於索引表是(____)的,可以採取類似(____)查找的快速定位演算法,在實際應用中,

摘要 由於索引表是排序的, 可以採取類似二分查找的快速定 位演算法,在實際應用中,索引表還可以駐留在主存儲器中,進一步提高查找的訪問速度。

Ⅹ 搜索引擎演算法中，什麼是正向索引什麼是倒排索引

倒排索引表中的每一項都包括一個屬性值和具有該屬性值的各記錄的地址。由於不是由記錄來確定屬性值，而是由屬性值來確定記錄的位置，因而稱為倒排索引(inverted index)。帶有倒排索引的文件我們稱為倒排索引文件，簡稱倒排文件。建立全文索引中有兩項非常重要，一個是如何對文本進行分詞，一是建立索引的數據結構。分詞的方法基本上是二元分詞法、最大匹配法和統計方法。索引的數據結構基本上採用倒排索引的結構。
分詞的好壞關繫到查詢的准確程度和生成的索引的大小。在中文分詞發展中，早期經常使用分詞方式是二元分詞法，該方法的基本原理是將包含中文的句子進行二元分割，不考慮單詞含義，只對二元單詞進行索引。因此該方法所分出的單詞數量較多，從而產生的索引數量巨大，查詢中會將無用的數據檢索出來，好處是演算法簡單不會漏掉檢索的數據。之後又發展出最大匹配分詞方法，該方法又分為正向最大分詞和逆向最大分詞。其原理和查字典類似，對常用單詞生成一個詞典，分析句子的過程中最大的匹配字典中的單詞，從而將句子拆分為有意義的單詞鏈。最大匹配法中正向分詞方法對偏正式詞語的分辨容易產生錯誤，比如「首飾和服裝」會將「和服」作為單詞分出。達夢資料庫採用的是改進的逆向最大分詞方法，該分詞方法較正向正確率有所提高。最為復雜的是通過統計方式進行分詞的方法。該方法採用隱式馬爾科夫鏈，也就是後一個單詞出現的概率依靠於前一個單詞出現的概率，最後統計所有單詞出現的概率的最大為分詞的依據。這個方法對新名詞和地名的識別要遠遠高於最大匹配法，准確度隨著取樣文本的數量的增大而提高。
二元分詞方法和統計方法是不依賴於詞典的，而最大匹配法分詞方法是依賴於詞典的，詞典的內容決定分詞結構的好壞。
全文檢索的索引被稱為倒排索引，之所以成為倒排索引，是因為將每一個單詞作為索引項，根據該索引項查找包含該單詞的文本。因此，索引都是單詞和唯一記錄文本的標示是一對多的關系。將索引單詞排序，根據排序後的單詞定位包含該單詞的文本。
步驟1）讀取一整條句子到變數str中，轉到步驟2

步驟2）從句子的尾端讀取1個字到變數word中，轉到步驟3

步驟3）在字典查找word中保存的單詞。如果存在則保存word，轉到步驟4，否則轉到步驟5）

步驟4）如果是字典中最大單詞或者超過最大單詞數（認定為新詞），從句尾去掉該單詞，返回步驟2

步驟5）讀取前一個字到word中，構成新單詞，轉到步驟3）

詞庫的內存數據結構和詞庫中單詞的匹配演算法

內存中單詞採用層次結構保存

假設字典中有如下的單詞：中國 中華民國 國家 人民 民主

在內存中按照如下方式按層排列，其中每一個方塊代表一個字，箭頭所指向為該單詞的前一個字