数据库之索引（Index） -

Lixh1986

浏览: 1112732 次

最近访客更多访客>>

Z865785437029

akingde

ningzong

蕃薯耀

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

数据库之索引（Index）

博客分类：

Algorithm

数据库索引 index 原理

在数据之外，数据库系统还维护着满足特定查找算法的数据结构。
这些数据结构以某种方式引用（指向）数据。
这样就可以在这些数据结构上实现高级查找算法。

——这种数据结构，就是索引。

数据库索引是数据库管理系统中一个排序的数据结构。以协助快速查询、更新数据库表中数据。

为表设置索引要付出代价的，
一是：增加了数据库的存储空间。
二是：在插入和修改数据时要花费较多的时间（因为索引也要随之变动）。

__________________________________________________________________________________

索引的实现之：B树及其变种B+树

一、B-树 ( Balanced Tree）

In computer science, a B-tree is a self-balancing tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree is a generalization of a binary search tree in that a node can have more than two children.
在计算机科学中，B树是自平衡树数据结构。其保持数据排序，并允许在对数时间内完成搜索、顺序存取、插入和删除。 B树是二叉搜索树的泛化，其节点可以具有多于两个的子节点。

Unlike self-balancing binary search trees, the B-tree is optimized for systems that read and write large blocks of data. B-trees are a good example of a data structure for external memory. It is commonly used in databases and filesystems.
与自平衡二叉搜索树不同的是，B树针对读取和写入大数据块的系统进行了优化。 B树是外部存储器的数据结构的一个很好的例子。它通常用于数据库和文件系统。

上图展示了一种可能的索引方式：
左边是数据表，一共有两列七条记录。
最左边的是数据记录的物理地址（注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的）。
为了加快 Col2 的查找，可以维护一个右边所示的二叉查找树，每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针。这样就可以运用二叉查找在 O(log2n) 的复杂度内获取到相应数据。

一棵三阶的 B-Tree

二、B+树 ( Balanced+ Tree）

B+的特性：
      1.所有数据都存储在叶子结点的链表中，且链表中的数据都是有序存放的；
      2.叶子节点间用指针相连。
      3.不可能在非叶子结点命中；
      4.非叶子结点相当于是叶子结点的索引，叶子结点相当于是存储数据的数据层；
      5.更适合文件索引系统；

B+的性能：等于在数据集合做一次二分查找；

一颗二阶的 B+Tree

与B-Tre的区别：
B+树只有达到叶子结点才命中。
B-树可以在非叶子结点命中。

A B+ tree is an n-ary tree with a variable but often large number of children per node.
A B+ tree consists of a root, internal nodes and leaves.The root may be either a leaf or a node with two or more children.
B+ 树是可变的 n 元树，通常每个节点具有大量子节点。
B+ 树由根，内部节点和叶组成。根可以是叶或具有两个或更多个子节点的节点。

A B+ tree can be viewed as a B-tree in which each node contains only keys (not key-value pairs), and to which an additional level is added at the bottom with linked leaves.
B+ 树可以被视为B树，其中每个（内部）节点仅包含键（不是键值对），并在其底部附加一层链式的叶子节点。

The primary value of a B+ tree is in storing data for efficient retrieval in a block-oriented storage context — in particular, filesystems.
This is primarily because unlike binary search trees, B+ trees have very high fanout (number of pointers to child nodes in a node, typically on the order of 100 or more), which reduces the number of I/O operations required to find an element in the tree.
B +树的主要价值在于存储数据，以便在面向块的存储上下文（特别是文件系统）中进行高效检索。
这主要是因为，与二叉搜索树不同的是，B +树具有非常高的扇出（节点中指向子节点的指针数，通常大约为100或更多），这减少了在树中查找元素所需的I / O操作数。

The ReiserFS, NSS, XFS, JFS, ReFS, and BFS filesystems all use this type of tree for metadata indexing;
BFS also uses B+ trees for storing directories.
NTFS uses B+ trees for directory indexing.
EXT4 uses extent trees (a modified B+ tree data structure) for file extent indexing.
Relational database management systems such as ：

IBM DB2,
Informix,
Microsoft SQL Server,
Oracle 8,
Sybase ASE,and
SQLite

support this type of tree for table indices.

Key-value database management systems such as ：（CouchDB and Tokyo Cabinet） support this type of tree for data access.

B+树索引被广泛应用于数据库、文件系统等场景。顺便说一下，xfs文件系统比ext3/ext4效率高很多的原因之一就是，它的文件及目录索引结构全部采用B+树索引，而ext3/ext4的文件目录结构则采用Linked list, hashed B-tree、Extents/Bitmap等索引数据结构，因此在高I/O压力下，其IOPS能力不如xfs。

详细可参见：

https://en.wikipedia.org/wiki/Ext4
https://en.wikipedia.org/wiki/XFS

_________________________________________________________________________________

创建索引可以大大提高系统的性能：

第一，可以显著提升数据的检索速度，这也是创建索引的最主要的原因。
第二，通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性。
第三，可以加速表和表之间的连接，特别是在实现数据的参考完整性方面特别有意义。
第四，在使用分组和排序子句进行数据检索时，同样可以显著减少查询中分组和排序的时间。
第五，通过使用索引，可以在查询的过程中，使用优化隐藏器，提高系统的性能。

增加索引也有许多不利的方面：

第一，创建索引和维护索引要耗费时间。这种时间随着数据量的增加而增加。
第二，索引需要占物理空间。除了数据表占数据空间之外，每一个索引还要占一定的物理空间。如果要建立聚簇索引，那么需要的空间就会更大。
第三，当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，这样就降低了数据的维护速度。

根据数据库的功能，可以在数据库设计器中创建三种索引：唯一索引、主键索引和聚集索引。

索引的实现之：Hash 索引

哈希索引采用哈希算法，把键值换算成哈希值，检索时不需要类似B+树那样从根节点到叶子节点逐级查找，只需一次哈希算法即可立刻定位到相应的位置，速度非常快。

从上面的图来看，B+树索引和哈希索引的明显区别是：

一、如果是等值查询，那么哈希索引明显有绝对优势。
因为只需要经过一次算法即可找到相应的键值；当然了，这个前提是，键值都是唯一的。如果键值不是唯一的，就需要先找到该键所在位置，然后再根据链表往后扫描，直到找到相应的数据；

二、如果是范围查询检索，这时候哈希索引就毫无用武之地了。
因为原先是有序的键值，经过哈希算法后，有可能变成不连续的了，就没办法再利用索引完成范围查询检索；哈希索引也没办法利用索引完成排序，以及like ‘xxx%’ 这样的部分模糊查询（这种部分模糊查询，其实本质上也是范围查询）；

三、哈希索引也不支持多列联合索引的最左匹配规则；
B+树索引的关键字检索效率比较平均，不像B树那样波动幅度大，在有大量重复键值情况下，哈希索引的效率也是极低的，因为存在所谓的哈希碰撞问题。

附：二分算法

在计算机科学中，
    二分搜索（binary search），
    也称折半搜索（half-interval search）、
    对数搜索（logarithmic search），
是一种在有序数组中查找某一特定元素的搜索算法。

这种搜索算法每一次比较都使搜索范围缩小一半。

引用

三分查找的时间复杂度分析

在网上搜索了一下有关三分查找时间复杂度分析的。有人说是O(3log3(n))，但是实验中三分比二分更耗时，所以他们就认为不能迷信时间复杂度。我现在纠正一下（仅个人分析，供网友参考）：
   1.二分查找的时间复杂度：因为每次都是折半，可以构造一颗递归树，共log2(n)层，每层只需O(1)的时间。所以共花费O(1)*log2(n)=O(log2(n))时间。
   2.而三分查找，也可类似构造一个递归树，共log3(n)层，而每层需要比较的次数为2，所以时间复杂度为
O(2log3(n))。

   求得使 2log3(n)>log2(n)   对n>0始终成立。

   所以三分查找比二分查找的性能就是差。

附：MySQL里常用的索引数据结构

在MySQL里常用的索引数据结构有两种：B+树索引和哈希索引。

在MySQL文档里，实际上是把B+树索引写成了BTREE，例如像下面这样的写法：

CREATE TABLE t(
    aid int unsigned not null auto_increment,
    userid int unsigned not null default 0,
    username varchar(20) not null default ‘’,
    detail varchar(255) not null default ‘’,
    primary key(aid),
    unique key(uid) USING BTREE,
    key (username(12)) USING BTREE — 此处 uname 列只创建了最左12个字符长度的部分索引
)engine=InnoDB;

--
引用：

数据库索引的实现原理
http://blog.csdn.net/kennyrose/article/details/7532032

B树、B-树、B+树、B*树
http://www.cnblogs.com/oldhorse/archive/2009/11/16/1604009.html

B-tree
https://en.wikipedia.org/wiki/B-tree

B+Tree
https://en.wikipedia.org/wiki/B%2B_tree

B+树索引和哈希索引的区别
http://imysql.com/2016/01/06/mysql-faq-different-between-btree-and-hash-index.shtml

二分搜索算法
https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%90%9C%E7%B4%A2%E7%AE%97%E6%B3%95

三分查找的时间复杂度分析
http://www.programgo.com/article/79762375640

_______________________________________________________________________________

HashMap之系列文章（一）：
Java之 equals() 和 hashCode() 之 HashMap

HashMap之系列文章（二）：
Java之HashMap深度学习

HashMap之系列文章（三）：
数据库之索引（Index）

HashMap之系列文章（四）：
Java之 HashMap VS. HashTable 区别

-