为什么数据库不用hash索引而用BTree索引 #21
Comments
|
B-tree，B是balance，一般用于数据库的索引。使用B-tree结构可以显著减少定位记录时所经历的中间过程，从而加快存取速度。而B+tree是B-tree的一个变种，大名鼎鼎的MySQL就普遍使用B+tree实现其索引结构。 那数据库为什么使用这种结构？ 一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。 为了达到这个目的，磁盘按需读取，要求每次都会预读的长度一般为页的整数倍。而且数据库系统将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。并把B-tree中的m值设的非常大，就会让树的高度降低，有利于一次完全载入。 m-way查找树 故，它的性质如下： 每个节点的键值数小于m
B-tree利用多个分支（称为子树）的结点，减少获取记录时所经历的结点数，从而达到节省存取时间的目的。 一棵度为m的B-tree应满足的性质： 每个结点的子结点个数≤m；
ki (1≤i≤j)是关键字，所有关键字的值是唯一的;pi (0≤i≤j)是指向该结点的子结点的指针 例如图中的P1，它指向的子树的关键字应该大于k1，小于k2 B-树的查找 B-tree的插入 插入的节点少于M-1个键值，则直接插入。 有几点不同的地方： 非叶子结点的子树指针与关键字个数相同
转自 http://www.cnblogs.com/coder2012/p/3330311.html 参考 http://blog.sina.com.cn/s/blog_6776884e0100ohvr.html http://baike.baidu.com/link?url=8Au1iocebretZtJN2E6JcIolkM79PDwQ22dJEESfntDvYUXHKfZ45s4zcd4PoCjm 更多-MySQL索引背后的数据结构及算法原理 |
|
其实这也是和业务场景相关的，你想想，数据库中select数据，不一定只选一条，很多时候会选多条，比如按照id排序后选10条。 |
不同的引擎对于索引有不同的支持：Innodb和MyISAM默认的索引是Btree索引；而Mermory默认的索引是Hash索引。 （）
Hash索引
哈希索引包含以数组形式组织的 Bucket 集合。 哈希函数将索引键映射到哈希索引中对应的 Bucket。 下图展示映射到哈希索引中三个不同 Bucket 的三个索引键。 出于演示目的，哈希函数的名称为 f(x)。
映射到不同 Bucket 的索引键。
用于哈希索引的哈希函数具有以下特征：
SQL Server 拥有一个用于所有哈希索引的哈希函数。
哈希函数具有确定性。 同一索引键始终映射到哈希索引中的同一 Bucket。
多个索引键可能映射到同一个哈希 Bucket。
哈希函数经过均衡处理，这意味着索引键值在哈希桶上的分布通常符合泊松分布。
泊松分布并非均匀分布。 索引键值并非均匀地分布在哈希 Bucket中。 例如，泊松分布的 n 非重复索引键通过 n 哈希桶中约三分之一空存储桶，包含一个索引键，则存储桶的三分之一的结果和其他第三个包含两个索引键。 少量 Bucket 将包含两个以上的键。
如果两个索引键映射到同一个哈希 Bucket，则产生哈希冲突。 大量哈希冲突可影响读取操作的性能。
内存哈希索引结构包含一个内存指针数组。 每个 Bucket 映射到该数组中的一个偏移位置。 数组中的每个 Bucket 指向该哈希 Bucket 中的第一行。 Bucket 中的每行指向下行，因而形成了每个哈希 Bucket 的行链，如下图所示。
内存中哈希索引结构。
该图有三个包含行的 Bucket。 顶部的第二个 Bucket 包含三个红色行。 第四个 Bucket 包含一个蓝色行。 底部的 Bucket 包含两个绿色行。 这些可能是同一行的不同版本。
所谓Hash索引，当我们要给某张表某列增加索引时，将这张表的这一列进行哈希算法计算，得到哈希值，排序在哈希数组上。所以Hash索引可以一次定位，其效率很高，而Btree索引需要经过多次的磁盘IO，但是innodb和myisam之所以没有采用它，是因为它存在着好多缺点：
1、因为Hash索引比较的是经过Hash计算的值，所以只能进行等式比较，不能用于范围查询
1、每次都要全表扫描
2、由于哈希值是按照顺序排列的，但是哈希值映射的真正数据在哈希表中就不一定按照顺序排列，所以无法利用Hash索引来加速任何排序操作
3、不能用部分索引键来搜索，因为组合索引在计算哈希值的时候是一起计算的。
4、当哈希值大量重复且数据量非常大时，其检索效率并没有Btree索引高的。
Btree索引
至于Btree索引，它是以B+树为存储结构实现的。
但是Btree索引的存储结构在Innodb和MyISAM中有很大区别。
在MyISAM中，我们如果要对某张表的某列建立Btree索引的话，如图：
所以我们经常会说MyISAM中数据文件和索引文件是分开的。
因此MyISAM的索引方式也称为非聚集，Innodb的索引方式成为聚集索引。
至于辅助索引，类似于主索引，唯一区别就是主索引上的值不能重复，而辅助索引可以重复。
因此当我们根据Btree索引去搜索的时候，若key存在，在data域找到其地址，然后根据地址去表中查找数据记录。
至于Innodb它跟上面又有很大不同，它的叶子节点存储的并不是表的地址，而是数据
我们可以看到这里并没有将地址放入叶子节点，而是直接放入了对应的数据，这也就是我们平常说到的，Innodb的索引文件就是数据文件，
那么对于Innodb的辅助索引结构跟主索引也相差很多，如图：
我们可以发现，这里叶子节点存储的是主键的信息，所以我们在利用辅助索引的时候，检索到主键信息，然后再通过主键去主索引中定位表中的数据，这就可以说明Innodb中主键之所以不宜用过长的字段，由于所有的辅助索引都包含主索引，所以很容易让辅助索引变得庞大。
我们还可以发现：在Innodb中尽量使用自增的主键，这样每次增加数据时只需要在后面添加即可，非单调的主键在插入时会需要维持B+tree特性而进行分裂调整，十分低效。
Btree索引中的最左匹配原则：
Btree是按照从左到右的顺序来建立搜索树的。比如索引是(name,age,sex)，会先检查name字段，如果name字段相同再去检查后两个字段。
所以当传进来的是后两个字段的数据（age，sex），因为建立搜索树的时候是按照第一个字段建立的，所以必须根据name字段才能知道下一个字段去哪里查询。
所以传进来的是（name，sex）时，首先会根据name指定搜索方向，但是第二个字段缺失，所以将name字段正确的都找到后，然后才会去匹配sex的数据。
建立索引的规则：
1、利用最左前缀：Mysql会一直向右查找直到遇到范围操作（>，<，like、between）就停止匹配。比如a=1 and b=2 and c>3 and d=6；此时如果建立了（a,b,c,d）索引，那么后面的d索引是完全没有用到，当换成了（a,b,d,c）就可以用到。
2、不能过度索引：在修改表内容的时候，索引必须更新或者重构，所以索引过多时，会消耗更多的时间。
3、尽量扩展索引而不要新建索引
4、最适合的索引的列是出现在where子句中的列或连接子句中指定的列。
5、不同值较少的列不必要建立索引（性别）。
The text was updated successfully, but these errors were encountered: