数据库索引,目前有树索引、哈希索引、全文索引等。
索引
索引是数据之外的一种数据结构,专门用来查找表中数据。
使用索引,可以大大加快检索速度,相应的,有获得必须有付出,我们需要话费额外的空间来存储索引。
索引这玩意儿,不像烧饼,做好了吃完就没了,索引有许多的优点,如:加快检索速度,数据无重复,加快表与表间的连接速度,有序的索引方便连续值查找。
索引这玩意儿,和其它的东西一样,既有优点又有缺点,它的缺点有:,创建和维护索引耗费时间、存储索引需要空间。
树索引
商业化的数据库中,一般都支持树索引,B-Tree 或 B+Tree。(实际上 B+Tree 使用更多)
和哈希索引相比,树索引的查找速度最慢会达到 O(LogN),但树索引是有序的。
哈希索引
哈希索引基于哈希表实现,将所有索引列(有时不只给一列数据建索引,要给两列三列甚至更多列建索引)结合起来,从而为每一行数据算出一个尽量独一无二的哈希值。
哈希值和该哈希值对应的数据行的行指针组合在一起,便是哈希表中的一行数据,N 行数据一起就是哈希表。
处理冲突
每当两个不同的数据拥有相同的哈希值,就意味着出现了冲突。冲突出现后,哈希索引会将彼此冲突的数据们串连起来,形成巨长的一条链(请别忘记我永远不变黄色的脸)
优点:
查找速度高达 O(1)。
缺点
- 只保存哈希值和行指针,不保存数据库中的数据;查找数据时,先计算数据的哈希值,使用该值来查找行指针,找到行指针后还要到数据库中验证,确保该数据行就是要查找的数据,所以每次查找都要
读行
。 - 哈希表数据无序,无法用于
排序
。 - 不支持
部分索引列
查找(建立了两列的索引,那就没法只用一列的数据来查找)。 - 索引维护
成本高
(如果哈希冲突很多,每从表中删除一行就要遍历整条冲突链,以便删除目标行)。 - 哈希值可能
冲突
。
全文索引
全文索引是一种特殊的索引,它并不直接匹配 Where 条件,不直接比较索引中的值,而是像搜索引擎那样,查找的是文本中的关键词。