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

今天，我在一个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次的比较。


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

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

评论

34 楼 kanny87929 2011-05-11  

songlu1002 写道

数据库的索引比楼主想象的要复杂的多。

其实我想说的不是数据库的索引

只是拿数据库的索引来举例子。

33 楼 songlu1002 2011-05-11  

数据库的索引比楼主想象的要复杂的多。

32 楼 ppgunjack 2011-05-11  

目录是索引，但索引不是目录
内存索引在执行文件链接表里大量存在，最后都会映射到进程空间，map就是典型的基于红黑的内存索引，map、内存<->文件映射是很多NOSQL序列化的实现
到现在也没人质疑帖子的索引查找成本分析

31 楼 ironpearl 2011-05-11  

LZ的举例浅显易懂。

30 楼 lemon_1227 2011-05-11  

就这么理解：  一本书内容很多吧，索引就是 书的目录。。。这样挺浅显易懂吧

29 楼 葬雪晴 2011-05-11  

索引是INDEX，也就是目录，建立索引的目的是为了快速的查找，另外数据库底层实现不一样，索引的数据结构也会不同，具体如何我也不是怎么清楚。

28 楼 informixca 2011-05-11  

数据库索引主要是为了减少读硬盘的次数，B+tree, R-tree 都是这个目的。
这是数据库索引存在的意义。
内存索引没有任何应用意义。

27 楼 ppgunjack 2011-05-10  

索即找，引即引用
这指的是种快速定位方式
理解成集合或分类规则是拿其某类实现解释定义
数组下标，rowid，指针地址，想对偏移，目录，hashkey均可看做是索引

26 楼 kjj 2011-05-10  

嗯,看了数据库概论这本书,索引实现基本是以树为主,查找树,

25 楼 gzyyygyf 2011-05-10  

索引就是一种提升查找速度的数据结构，通常用tree结构实现的，你了解tree的话也就了解了索引

24 楼 kanny87929 2011-05-10  

AllenZhang 写道

什么聚类，非聚类，map都是粗浅的浮云。
索引的本质就是分类规则。

23 楼 mlc880926 2011-05-10  

AllenZhang 写道

什么聚类，非聚类，map都是粗浅的浮云。
索引的本质就是分类规则。

22 楼 kakaluyi 2011-05-10  

楼主用很浅显的例子解释了b+树?

21 楼 AllenZhang 2011-05-10  

什么聚类，非聚类，map都是粗浅的浮云。
索引的本质就是分类规则。

20 楼 lyl290932857 2011-05-10  

基本概念还说的可以。

19 楼 kanny87929 2011-05-10  

xzk3761 写道

数据库最基本的索引的理解,就像你说的"一个已经按照一定规则排序好的数据结构或数据集".

更多的索引的理解,说法,实现等可能不同,但最基本的理念可能是基于这句话.

像数据库,不管是位图索引,tree索引或者其他,目的在于加快查询速度,都有自己完整的一套数据结构.

还是这位仁兄理解我这样定义的意义。感谢大家一起讨论。

18 楼 guoqingcun 2011-05-10  

索引有待深入理解...共免之...加油

17 楼 xzk3761 2011-05-10  

数据库最基本的索引的理解,就像你说的"一个已经按照一定规则排序好的数据结构或数据集".

更多的索引的理解,说法,实现等可能不同,但最基本的理念可能是基于这句话.

像数据库,不管是位图索引,tree索引或者其他,目的在于加快查询速度,都有自己完整的一套数据结构.

16 楼 mainlove 2011-05-10  

查询时的数据集发生了改变，原来一行行找下来要找38511次，现在按照这个索引结构找下来要85536次

那如果这个时候38511前面的数据被删了100个  怎么办？

难道还从38511 开始找吗？ 这个时候它是怎么调整策略的

15 楼 PineSeed 2011-05-10  

感谢楼周的分享，举的例子很生动容易理解。最近刚好学习到，本来还计较模糊，看到这个突然明白了很多。再次感谢