数据库索引

无论是传统的关系型数据库,还是比较新型的Nosql数据库MongoDB 都需要合理使用索引加快搜索速度

索引和数据的关系和目录与正文的关系一样

索引本身并不记录真正内容信息,他只是记录真正信息的的存储位置(比如使用Hash来记录数据使得查找成本为O(1)的HashMap (java)中)

索引就是这样的东西,根据数据库使用的存储引擎的不同,索引项中存储的东西也不尽相同.但只要明白每一条存储项里放着 "什么东西"放在了"什么地方"就行了

稀疏索引和稠密索引

有了索引之后,查找就从扫描每一个文件块中的每一个元组变成了扫描了每一条索引项
可以为每一条元组写一条索引.这样的方式称为稠密索引,这样的索引问题在于元组数量多了
索引数量也会很多.

但索引一般都是按照某个属性的某个顺序来排列的,(比如按身高的高低排列)
那么完全可以"跳着"写索引

比如,写个身高160 在 xxx位置,170在yyy位置
那么查找身高165 只需要找到160,接着从xxx位置开始搜索,找165
如果到了yyy还没有找到,就是没有了

这样的索引称为稀疏索引

从某种程度上缓解了稠密索引在元组多了之后索引变多带来的查找效率变低的情况

还有一种解决方式是采用多级索引:给索引写索引

比如10000本的百科全书,可能需要为他写一个目录书:
计算机科学的在xx柜子的yy层,然后每本百科全书都有自己的目录

再比如有100万本百科全书,你还可以再写一个目录,计算机科学的书在哪个图书馆
然后该图书馆有自己的目录计算机科学在哪个柜子上

再比如有100亿本百科全书,可以写这样一个索引:计算机科学的书在XX星球...

主索引和辅助索引

主索引就是聚集索引,数据元组也是按照该索引的属性来排序的

辅助索引就是索引其他属性的索引了

需要注意的是辅助索引只适于稠密索引~

原因很很清楚- -

增加索引带来效率问题

索引的存在为查询提供了便利,但是却麻烦了增 删 改

索引也是记录,若索引按照顺序文件的形式存放,那么增加了某条记录后需要修改索引也将成为大问题

如果有冗余还好,如果没有就很麻烦了

所以一般情况下,并不会使用这样的多级顺序索引的方式,而是采用 B树或者B+树这样的
数据结构来组织索引

关于b树和b+树,请参考算法导论- -

复合码索引

索引项可以由多个属性来产生

比如用(收入,性别)生成索引
这样可以快速帮你找到输入高的男性了

还可以更丧心病狂的将(收入,性别,年龄)来生成索引~~方便继承遗产什么的- -
符合索引可以使用R树来组织

散列索引

像java中的HashMap结构,查询数据的查找成本为O(1)的方式组织数据也是可行的

根据需要的属性的具体值用某种函数计算出一个值,这个值界定这条记录所处的位置

查询时也只是需要计算这个函数,就可以知道他的位置了

一般请款改下,这个"位置"称为"桶",可以使磁盘块,也可以是其他什么的顺序结构

如果桶的大小是确定的,那么这种方式称为静态散列,这种方法无可避免的要遇到桶溢出问题

否则称为动态散列

比较B+树和顺序文件组成的索引和 散列索引

如果查询多为点查询 比如 where age = 30
使用散列很方便

但如果是范围查询
那么 B+树和顺序文件组成的索引将更有效

sql中建立索引

create index <name> on <relation-name> ( <attrobute-name>)