無論是傳統(tǒng)的關(guān)系型數(shù)據(jù)庫,還是比較新型的Nosql數(shù)據(jù)庫MongoDB 都需要合理使用索引加快搜索速度
索引和數(shù)據(jù)的關(guān)系和目錄與正文的關(guān)系一樣
索引本身并不記錄真正內(nèi)容信息,他只是記錄真正信息的的存儲(chǔ)位置(比如使用Hash來記錄數(shù)據(jù)使得查找成本為O(1)的HashMap (java)中)
索引就是這樣的東西,根據(jù)數(shù)據(jù)庫使用的存儲(chǔ)引擎的不同,索引項(xiàng)中存儲(chǔ)的東西也不盡相同.但只要明白每一條存儲(chǔ)項(xiàng)里放著 "什么東西"放在了"什么地方"就行了
稀疏索引和稠密索引
有了索引之后,查找就從掃描每一個(gè)文件塊中的每一個(gè)元組變成了掃描了每一條索引項(xiàng)
可以為每一條元組寫一條索引.這樣的方式稱為稠密索引,這樣的索引問題在于元組數(shù)量多了
索引數(shù)量也會(huì)很多.
但索引一般都是按照某個(gè)屬性的某個(gè)順序來排列的,(比如按身高的高低排列)
那么完全可以"跳著"寫索引
比如,寫個(gè)身高160 在 xxx位置,170在yyy位置
那么查找身高165 只需要找到160,接著從xxx位置開始搜索,找165
如果到了yyy還沒有找到,就是沒有了
這樣的索引稱為稀疏索引
從某種程度上緩解了稠密索引在元組多了之后索引變多帶來的查找效率變低的情況
還有一種解決方式是采用多級(jí)索引:給索引寫索引
比如10000本的百科全書,可能需要為他寫一個(gè)目錄書:
計(jì)算機(jī)科學(xué)的在xx柜子的yy層,然后每本百科全書都有自己的目錄
再比如有100萬本百科全書,你還可以再寫一個(gè)目錄,計(jì)算機(jī)科學(xué)的書在哪個(gè)圖書館
然后該圖書館有自己的目錄計(jì)算機(jī)科學(xué)在哪個(gè)柜子上
再比如有100億本百科全書,可以寫這樣一個(gè)索引:計(jì)算機(jī)科學(xué)的書在XX星球...
主索引和輔助索引
主索引就是聚集索引,數(shù)據(jù)元組也是按照該索引的屬性來排序的
輔助索引就是索引其他屬性的索引了
需要注意的是輔助索引只適于稠密索引~
原因很很清楚- -
增加索引帶來效率問題
索引的存在為查詢提供了便利,但是卻麻煩了增 刪 改
索引也是記錄,若索引按照順序文件的形式存放,那么增加了某條記錄后需要修改索引也將成為大問題
如果有冗余還好,如果沒有就很麻煩了
所以一般情況下,并不會(huì)使用這樣的多級(jí)順序索引的方式,而是采用 B樹或者B+樹這樣的
數(shù)據(jù)結(jié)構(gòu)來組織索引
關(guān)于b樹和b+樹,請(qǐng)參考算法導(dǎo)論- -
復(fù)合碼索引
索引項(xiàng)可以由多個(gè)屬性來產(chǎn)生
比如用(收入,性別)生成索引
這樣可以快速幫你找到輸入高的男性了
還可以更喪心病狂的將(收入,性別,年齡)來生成索引~~方便繼承遺產(chǎn)什么的- -
符合索引可以使用R樹來組織
散列索引
像java中的HashMap結(jié)構(gòu),查詢數(shù)據(jù)的查找成本為O(1)的方式組織數(shù)據(jù)也是可行的
根據(jù)需要的屬性的具體值用某種函數(shù)計(jì)算出一個(gè)值,這個(gè)值界定這條記錄所處的位置
查詢時(shí)也只是需要計(jì)算這個(gè)函數(shù),就可以知道他的位置了
一般請(qǐng)款改下,這個(gè)"位置"稱為"桶",可以使磁盤塊,也可以是其他什么的順序結(jié)構(gòu)
如果桶的大小是確定的,那么這種方式稱為靜態(tài)散列,這種方法無可避免的要遇到桶溢出問題
否則稱為動(dòng)態(tài)散列
比較B+樹和順序文件組成的索引和 散列索引
如果查詢多為點(diǎn)查詢 比如 where age = 30
使用散列很方便
但如果是范圍查詢
那么 B+樹和順序文件組成的索引將更有效
sql中建立索引
create index <name> on <relation-name> ( <attrobute-name>)
