数据库索引
- - CSDN博客推荐文章索引是由用户创建的、能够被修改和删除的、实际存储于数据库中的物理存在；创建索引的目的是使用户能够从整体内容直接查找到某个特定部分的内容. 一般来说，索引能够提高查询，但是会增加额外的空间消耗，并且降低删除、插入和修改速度. 1.聚集索引：表数据按照索引的顺序来存储的. 2.非聚集索引：表数据存储顺序与索引顺序无关.
数据库索引
标签：
数据库
索引
| 发表时间：2012-03-14 21:09 | 作者：yfkiss
出处：http://blog.csdn.net
概念：
索引是由用户创建的、能够被修改和删除的、实际存储于数据库中的物理存在；创建索引的目的是使用户能够从整体内容直接查找到某个特定部分的内容。
优缺点：
一般来说，索引能够提高查询，但是会增加额外的空间消耗，并且降低删除、插入和修改速度
分类：
1.聚集索引：表数据按照索引的顺序来存储的。
2.非聚集索引：表数据存储顺序与索引顺序无关。
由于聚集索引表的数据需要按照索引的顺序来存储，因此，一张表上只能创建一个聚集索引，非聚集索引则没有这方面的限制
聚集索引对于那些经常要搜索范围值的列或者查询时经常需要对某列进行排序的情况特别有效，但是由于需要保证数据和索引顺序的一致性，会带来对数据增删改效率降低。
常用索引数据结构：
多叉平衡搜索树：B树 / B+树 / B*树
B树
1. d为大于1的一个正整数，称为B-Tree的 度。
2. h为一个正整数，称为B-Tree的 高度。
3. 每个非叶子节点由n-1个key和n个指针组成，其中d<=n<=2d。
4. 每个叶子节点最少包含一个key和两个指针，最多包含2d-1个key和2d个指针，叶节点的指针均为null 。
5. 所有叶节点具有相同的深度，等于树高h。
6. key和指针互相间隔，节点两端是指针。
7. 一个节点中的key从左到右非递减排列。
8. 所有节点组成树结构。
9. 每个指针要么为null，要么指向另外一个节点。
10. 如果某个指针在节点node最左边且不为null，则其指向节点的所有key小于v(key1)，其中v(key1)为node的第一个key的值。
11. 如果某个指针在节点node最右边且不为null，则其指向节点的所有key大于v(keym)，其中v(keym)为node的最后一个key的值。
12. 如果某个指针在节点node的左右相邻key分别是keyi和keyi+1且不为null，则其指向节点的所有key小于v(keyi+1)且大于v(keyi)。
图：
B+树及B*树都是B树的变种，和B树相比，B+树：
1.每个节点的指针上限为2d而不是2d+1。
2.内节点不存储data，只存储key；叶子节点不存储指针。
B*树则在B+树的基础上，在内节点上增加了指向兄弟的指针。
数据库面对的常常是海量数据，即使索引也常常放到外存而不是内存。由于多叉树树的高度低，为了尽量减少访问磁盘的次数，采用多叉树而不是二叉树的结构。
Mysql MYISAM及InnoDB引擎采用的是B+树作为索引结构。区别在于，MYISAM采用的非聚集式索引，InnoDB采用的聚集式索引。
Hash索引：
和B树索引相比，Hash索引查询更快，但是其也有一些问题
1. 和Hash索引相比，B+树更适合作为外存索引（Extensible Hash Tables和 Linear Hash Tables可以作为外存索引）
2. 不支持范围查询；在组合键作为索引的情况下，无法使用部分键值做查询；.不能通过索引进行键值排序；
3. 由于Hash值有可能冲突，所以即使取满足某个 Hash 键值的数据的记录条数，也无法从 Hash 索引中直接完成查询，还是要通过访问表中的实际数据进行相应的比较。
位图索引：
位图索引是针对那些低基数，并且值不经常改变的列的。
位图索引并不适用于OLTP业务，OLTP一般都是有大量的并发事务来修改同样的数据。bitmap主要就是设计来为数据仓库服务的，即应用于低基数超级大数据量查询服务，而且只用在where clause里包含and ,or,not,或equalityqueries（比如在and和or条件的查询，在把bit转换成rowid以前，就能很快的得到相应的boolean操作）。
扩展阅读可以参看reference中位图相关内容。
reference：
Introduction to Database Indexes： http://www.interspire.com/content/2006/02/15/introduction-to-database-indexes/
wiki ： http://en.wikipedia.org/wiki/Database_index
MySQL索引背后的数据结构及算法原理：http://www.codinglabs.org/html/theory-of-mysql-index.html
书：海量数据库解决方案
bitmap位图索引：http://www.blogjava.net/leekiang/archive/2008/06/25/210564.html
Oracle编程高手箴言：位图索引(Bitmap Index)的故事 ：http://blog.csdn.net/carlwu/article/details/2319584
位图索引简介：http://www.baidot.com/tech/database/97ce9e31-948a-412b-8846-a2698cdfaf4d.aspx
索引是由用户创建的、能够被修改和删除的、实际存储于数据库中的物理存在；创建索引的目的是使用户能够从整体内容直接查找到某个特定部分的内容。
优缺点：
一般来说，索引能够提高查询，但是会增加额外的空间消耗，并且降低删除、插入和修改速度
分类：
1.聚集索引：表数据按照索引的顺序来存储的。
2.非聚集索引：表数据存储顺序与索引顺序无关。
由于聚集索引表的数据需要按照索引的顺序来存储，因此，一张表上只能创建一个聚集索引，非聚集索引则没有这方面的限制
聚集索引对于那些经常要搜索范围值的列或者查询时经常需要对某列进行排序的情况特别有效，但是由于需要保证数据和索引顺序的一致性，会带来对数据增删改效率降低。
常用索引数据结构：
多叉平衡搜索树：B树 / B+树 / B*树
B树
1. d为大于1的一个正整数，称为B-Tree的 度。
2. h为一个正整数，称为B-Tree的 高度。
3. 每个非叶子节点由n-1个key和n个指针组成，其中d<=n<=2d。
4. 每个叶子节点最少包含一个key和两个指针，最多包含2d-1个key和2d个指针，叶节点的指针均为null 。
5. 所有叶节点具有相同的深度，等于树高h。
6. key和指针互相间隔，节点两端是指针。
7. 一个节点中的key从左到右非递减排列。
8. 所有节点组成树结构。
9. 每个指针要么为null，要么指向另外一个节点。
10. 如果某个指针在节点node最左边且不为null，则其指向节点的所有key小于v(key1)，其中v(key1)为node的第一个key的值。
11. 如果某个指针在节点node最右边且不为null，则其指向节点的所有key大于v(keym)，其中v(keym)为node的最后一个key的值。
12. 如果某个指针在节点node的左右相邻key分别是keyi和keyi+1且不为null，则其指向节点的所有key小于v(keyi+1)且大于v(keyi)。
图：
B+树及B*树都是B树的变种，和B树相比，B+树：
1.每个节点的指针上限为2d而不是2d+1。
2.内节点不存储data，只存储key；叶子节点不存储指针。
B*树则在B+树的基础上，在内节点上增加了指向兄弟的指针。
数据库面对的常常是海量数据，即使索引也常常放到外存而不是内存。由于多叉树树的高度低，为了尽量减少访问磁盘的次数，采用多叉树而不是二叉树的结构。
Mysql MYISAM及InnoDB引擎采用的是B+树作为索引结构。区别在于，MYISAM采用的非聚集式索引，InnoDB采用的聚集式索引。
Hash索引：
和B树索引相比，Hash索引查询更快，但是其也有一些问题
1. 和Hash索引相比，B+树更适合作为外存索引（Extensible Hash Tables和 Linear Hash Tables可以作为外存索引）
2. 不支持范围查询；在组合键作为索引的情况下，无法使用部分键值做查询；.不能通过索引进行键值排序；
3. 由于Hash值有可能冲突，所以即使取满足某个 Hash 键值的数据的记录条数，也无法从 Hash 索引中直接完成查询，还是要通过访问表中的实际数据进行相应的比较。
位图索引：
位图索引是针对那些低基数，并且值不经常改变的列的。
位图索引并不适用于OLTP业务，OLTP一般都是有大量的并发事务来修改同样的数据。bitmap主要就是设计来为数据仓库服务的，即应用于低基数超级大数据量查询服务，而且只用在where clause里包含and ,or,not,或equalityqueries（比如在and和or条件的查询，在把bit转换成rowid以前，就能很快的得到相应的boolean操作）。
扩展阅读可以参看reference中位图相关内容。
reference：
Introduction to Database Indexes： http://www.interspire.com/content/2006/02/15/introduction-to-database-indexes/
wiki ： http://en.wikipedia.org/wiki/Database_index
MySQL索引背后的数据结构及算法原理：http://www.codinglabs.org/html/theory-of-mysql-index.html
书：海量数据库解决方案
bitmap位图索引：http://www.blogjava.net/leekiang/archive/2008/06/25/210564.html
Oracle编程高手箴言：位图索引(Bitmap Index)的故事 ：http://blog.csdn.net/carlwu/article/details/2319584
位图索引简介：http://www.baidot.com/tech/database/97ce9e31-948a-412b-8846-a2698cdfaf4d.aspx
作者：yfkiss 发表于2012-3-14 21:09:02 原文链接
阅读：15 评论：0 查看评论
相关 [数据库 索引] 推荐：
数据库索引总结
- - CSDN博客数据库推荐文章一、为什么要创建索引呢（优点）. 这是因为，创建索引可以大大提高系统的性能. 第一， 通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性. 第二， 可以大大加快数据的检索速度，这也是创建索引的最主要的原因. 第三， 可以加速表和表之间的连接，特别是在实现数据的参考完整性方面特别有意义.
数据库索引的使用
- - CSDN博客数据库推荐文章使用索引有很多优点，例如可以大大提高数据库的检索速度，改善数据库性能;. 可以在查询的过程中使用优化隐藏器，提高系统的性能等. 但是增加索引也会存在着缺陷，例如：. 1.创建索引和维护索引要耗费时间;. 2.索引需要占物理空间，除了数据表占数据空间之外，每一个索引还要占一定的物理空间;. 3.当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，这样就降低了数据的维护速度.
理解MySQL数据库覆盖索引
- - haohtml's blog看AUTO_INCREMENT就知道数据并不多，75万条. 很简单对不对?怪异的地方在于：. 如果换成MyISAM做存储引擎的时候，查询耗时只需要0.01s，用InnoDB却会是0.15s左右. 如果只是就这么点差距其实不是什么大不了的事，但是真实的业务需求比这个复杂，造成的差距也很大：MyISAM只需要0.12s，InnoDB则需要2.2s.，最终定位到问题症结是在这条SQL.
数据库索引的实现原理
- - 孟飞阳的博客说白了，索引问题就是一个查找问题. 二、数据库索引介绍及特点说明. 数据库索引，是数据库管理系统中一个排序的数据结构，以协助快速查询、更新数据库表中数据. 索引的实现通常使用B树及其变种B+树. 在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法.
数据库查询性能优化之利器—索引（一）
- - 博客园_首页 数据库查询性能优化之利器—索引（一）. 最近在做基于Android的公交查询系统的过程中，遇到一个很棘手的问题：换乘算法效率低. 在直达查询和一次换乘查询的时候，问题体现的还不是很明显，能够在1s之内查询出乘车方案，而当进行二次查询的时候，基本要等一两分钟才能查询出换乘方案，这对于公交查询系统是绝对无法容忍的.
Mysql数据库索引查询优化的分享
- - 膘叔这是昨天SAE分享的一篇文章，开始的时候，我看了一遍，发现好象没有什么特别的内容，但再仔细看的时候，发现居然可以这样做. 我们要访问的表是一个非常大的表，四千万条记录，id是主键，program_id上建了索引. 执行一条SQL:. 这条SQL非常慢. 我们原以为处理记录太多的原因，所以加了id限制，一次只读五十万条记录.
数据库优化-删除不再使用的索引
- - CSDN博客数据库推荐文章一个运行了四年的库，近期发现一些头疼的问题，空间不足，性能降低. 发现有些索引因为应用变更，基本不用了，决定检测，删除那些不同的索引；. 以前也有写过博文： http://blog.csdn.net/jacson_bai/article/details/37773319. 这里涉及到公司一些安全，就不贴出来了，主要说一下解决思路.
数据库索引的作用和优点缺点
- - 数据库 - ITeye博客这是因为，创建索引可以大大提高系统的性能. 第一，通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性. 第二，可以大大加快 数据的检索速度，这也是创建索引的最主要的原因. 第三，可以加速表和表之间的连接，特别是在实现数据的参考完整性方面特别有意义. 第四，在使用分组和排序 子句进行数据检索时，同样可以显著减少查询中分组和排序的时间.
如何成为建数据库索引的高手？
- - 数据库 - ITeye博客今天来聊聊数据库里的索引，你知道的，网上这样的文章一抓一大把的， 基本都是从索引的原理说起，讲到索引的分类， 物理组织和存储形式，如何找到对应的记录，如何构建复杂的索引等等 ，如果我再写一篇这样的就没意思了，而且这些未必真的是大家（尤其是开发同学）关心的. 所以我今天打算以一个不同的角度来讲下索引，而且针对B+tree索引，希望大家看了会有所帮助.