到底对“索引”怎么样理解

今天，我在一个java群和别人讨论对索引的理解问题。
大家说了半天我都无法理解他们在说什么。
我还在网上查看了很多关于索引的定义，
但都是太笼统没有比喻也没有具体的例子。

最后我只能说出我对索引的理解。

我个人定义索引是：一个已经按照一定规则排序好的数据结构或数据集。

下面举例

例子1：

现在有一张表，里面有10W行数据，其中有一个列，列的名字叫name,数据类型为字符串
现在要查询一个name为tom的，好，现在在name上建立一个数据库默认的索引。
我相信，大多数数据库对字符串类型的列，默认都是按字母升序排列的。
首先查看了一下第一个有tom的这行数据出现在表的第38511行
建立索引后按照我原先的简单按字母升序排序，第一个出现有tom的这行数据排列到了85536行
如果按照这个索引结构来查询第一个出现tom的话还比没有建立这个索引时要慢，原因很简单。
查询时的数据集发生了改变，原来一行行找下来要找38511次，现在按照这个索引结构找下来要85536次

但默认的索引结构也许不是这样的。也许它套用了一个树结构，这个树也许就2层
第一层是按字符串首字母升序排序好的单个字母a,b,c,d,e,f,g,h....,（其中也许字母x没有，这也是有可能的）
第二层是按字符串首字母归类好的数据集合，并且每个集合按字母升序也是排序好的。

那么查询tom的时候，检查到tom是在第一层树的第20字母上，也就是t,查询这一层只花了20次比较
然后在第二层的以T字母开头排序好的数据集中发现tom在这个数据集的第16行。

那么按照这个索引结构查询name为tom的数据行最快的只要比较20+16次就可以找到第一个符合的数据

但如果tom这行数据在表里就排在第10行，那么按照上面的索引结构搜索找到所花的时间还要长。

例子2：

现在有一张表，里面有10W行数据，其中有一个列，列的名字叫id，类型整数，
现在要查询一个id为83111的。现在在id上建立一个数据库默认的索引
我相信，大多数数据库对默认的整数类型的列，都是按数字升序排列的。
首先查看了一下第一个有83111的这行数据排列在83111行
建立索引后按照原先的简单按数字升序排序，第一个出现有83111的这行数据还是出现在表的第83111行
如果按照这个索引结构来查询第一个出现id为83111的话和没有建立这个索引时一样的速度。原因还是很简单。
查询时的数据集和表集是一样的。

但默认的索引结构也许不是这样的，也许它套用了一个树结构，这个树也许就2层
第一层每个支点为，>=0 & <= 9999, >=10000 & <= 19999, 这样一直下去，
节点的最大一个范围取决于id最大的一个数它所在的那个范围。
第二层是在某一个范围内已经按数字升序排列好的数据集。
那么查找83111这个id，先比较第一层的范围，发现83111在，>=80000 & <=89999 中，第一层比较了9次，
然后在这个范围内在查找83111，发现在3112行，也就是比较了3112次
最后找到这个数总共才花了3112+9次的比较。


通过举例终于可以理解为什么要建立索引，和建立索引的优点和缺点。
看来建立索引要有很强的排序算法支持。

不知道大家看懂了吗，同意我个人对索引的定义吗？

评论

14 楼 zhaoruiqing 2011-05-10  

ppgunjack 写道

map也是索引的一种实现，数据库索引其实就是索引列和物理地址的一种映射
定位单条数据不可能有索引和没索引速度一样，不管数据物理存贮顺序如何

+1
再有。。。别人说什么你不知道的时候是不是该问问额~~

13 楼 ppgunjack 2011-05-10  

map也是索引的一种实现，数据库索引其实就是索引列和物理地址的一种映射
定位单条数据不可能有索引和没索引速度一样，不管数据物理存贮顺序如何

12 楼 anyasir 2011-05-10  

感谢楼主的举例

11 楼 mxswl 2011-05-10  

聚集索引，辅助索引。

10 楼 wl95421 2011-05-10  

首先，索引是一个复杂的问题。
所以，先要让大家通过简单的场景，来有一个简单的概念。
在这个基础上，再深入去根据相应的业务去找相应的东西。
不要一开始就太理论化，或者说下一个定义。
太空的定义，很难理解的。

9 楼 javantsky 2011-05-10  

哥们你在臆想了，索引比你描述的复杂多了

8 楼 xiaoxiao_0311 2011-05-10  

这位同学，请先说清楚这是你对数据库中索引的理解，在搜索领域还有其它的索引，所以索引的概念会比较泛，因为它覆盖范围广。在数据库中有聚集索引和非聚焦索引，这在数据库原理中都有讲到，可以参考下。聚集索引会改变记录的物理位置，像你的例子1 ，只是像啊，别理解错，现在还有技术是建立索引表，类似你的例子2，还有其它技术。。。在数据库之外还有其它的索引概念，比如在搜索引擎中，是这样定义的：从非结构化的数据中提取出数据并使之结构化以提高搜索速度，这部分信息就称为索引（参考lucene原理与代码分析完整版）。你的例子1 只考虑个例，却没考虑平均性能，求一下平均查找时间。当然个别的也会出现比索引前更慢的可能，这时就需要一些算法了，最简单的比如二分，还比如hash等。。。再对楼上更正一点，不是所有索引都会改变结果集的，比如之前提到的非聚集索引。

7 楼 wu_quanyin 2011-05-10  

kanny87929 写道

wl95421 写道

举个简单的例子：
1、正常的情况是一个句子能告诉别人句子中包含什么词
2、索引是告诉别人某个词在哪些句子中。
两者正好相反。

很多人都很想知道，索引怎么告诉某个词在哪些句子中的
所以很多次遇到这样的回答，你就无法理解为什么是这样的回答
所以必须举出例子，告诉大家，原来索引改变了原来结果集，
把原来结果集归类排序了，查找的时候减少了比较的次数。

索引测试

6 楼 tianshiyeben 2011-05-10  

醍醐灌顶  楼主分析的很透彻

5 楼 kanny87929 2011-05-10  

wl95421 写道

举个简单的例子：
1、正常的情况是一个句子能告诉别人句子中包含什么词
2、索引是告诉别人某个词在哪些句子中。
两者正好相反。

很多人都很想知道，索引怎么告诉某个词在哪些句子中的
所以很多次遇到这样的回答，你就无法理解为什么是这样的回答
所以必须举出例子，告诉大家，原来索引改变了原来结果集，
把原来结果集归类排序了，查找的时候减少了比较的次数。

4 楼 wl95421 2011-05-10  

举个简单的例子：
1、正常的情况是一个句子能告诉别人句子中包含什么词
2、索引是告诉别人某个词在哪些句子中。
两者正好相反。

3 楼 naoda 2011-05-10  

非常通俗易懂 受益非浅

2 楼 kanny87929 2011-05-10  

weilingfeng98 写道

说的很清楚

没办法，概念模糊，必须写一大堆来说清楚

1 楼 weilingfeng98 2011-05-09  

说的很清楚