建设个网站要多少钱,沈阳智能模板建站,技术支持海安网站建设,水果电子商务网站建设规划书1. 索引的各种存储结构及其优缺点
1.1 二叉树 优点#xff1a; 二叉树是一种比顺序结构更加高效地查找目标元素的结构#xff0c;它可以从第一个父节点开始跟目标元素值比较#xff0c;如果相等则返回当前节点#xff0c;如果目标元素值小于当前节点#xff0c;则移动到左…1. 索引的各种存储结构及其优缺点
1.1 二叉树 优点 二叉树是一种比顺序结构更加高效地查找目标元素的结构它可以从第一个父节点开始跟目标元素值比较如果相等则返回当前节点如果目标元素值小于当前节点则移动到左侧子节点进行比较大于的情况则移动到右侧子节点进行比较反复进行操作最终移动到目标元素节点位置。 缺点
在大部分情况下我们设计索引时都会在表中提供一个自增整形字段作为建立索引的列在这种场景下使用二叉树的结构会导致我们的索引总是添加到右侧在查找记录时跟没加索引的情况是一样的
1.2 红黑树
优点
红黑树也叫平衡二叉树它不仅继承了二叉树的优点而且解决了上面二叉树遇到的自增整形索引的问题从下面的动态图中可以看出红黑树会左旋、右旋对结构进行调整始终保证左子节点数 父节点数 右子节点数的规则。
缺点
在数据量大的时候深度也很大。从图中可以看出每个父节点只能存在两个子节点如果我们有很多数据那么树的深度依然会很大可能就会超过十几二十层以上对我们的磁盘寻址不利依然会花费很多时间查找。
1.3 Hash
优点
对数据进行Hash散列运算主流的Hash算法有MD5、SHA256等等然后将哈希结果作为文件指针可以从索引文件中获得数据的文件指针再到数据文件中获取到数据按照这样的设计我们在查找where Col2 22的记录时只需要对22做哈希运算得到该索引所对应那行数据的文件指针从而在MySQL的数据文件中定位到目标记录查询效率非常高。
缺点
无法解决范围查询Range的场景比如 select count(id) from sus_user where id 10因此Hash这种索引结构只能针对字段名目标值的场景使用。不适合模糊查询like的场景。
1.4 B-Tree
既然红黑树存在缺点那么我们可以在红黑树的基础上构思一种新的储存结构。解决的思路也很简单既然觉得树的深度太长就只需要适当地增加每个树节点能存储的数据个数即可但是数据个数也必须要设定一个合理的阈值不然一个节点数据个数过多会产生多余的消耗。
1.4.1 B-Tree的一些特点
度(Degree)-节点的数据存储个数每个树节点中数据个数大于 15/16*Degree未验证 时会自动分裂调整结构叶节点具有相同的深度左子树跟右子树的深度一致叶节点的指针为空节点中的数据key从左到右递增排列
优点
BTree的结构可以弥补红黑树的缺点解决数据量过大时整棵树的深度过长的问题。相同数量的数据只需要更少的层相同深度的树可以存储更多的数据查找的效率自然会更高。
缺点
从上面得知在查询单条数据是非常快的。但如果范围查的话BTree结构每次都要从根节点查询一遍效率会有所降低因此在实际应用中采用的是另一种BTree的变种BTreeB树。
2. BTree—InnoDB中的索引方案
2.1 相对于BTreeBTree做了哪些优化
BTree存储结构只有叶子节点存储数据 。新的B树结构没有在所有的节点里存储记录数据而是只在最下层的叶子节点存储上层的所有非叶子节点只存放索引信息这样的结构可以让单个节点存放下更多索引值增大度Degree的值提高命中目标记录的几率。
这种结构会在上层非叶子节点存储一部分冗余数据但是这样的缺点都是可以容忍的因为冗余的都是索引数据不会对内存造成大的负担。这种结构会在上层非叶子节点存储一部分冗余数据但是这样的缺点都是可以容忍的因为冗余的都是索引数据不会对内存造成大的负担。 InnoDB中的索引是通过目录项所指向的下一层页号来一层一层去缩小搜索范围从而达到高效的查询的。通过二分法对页内的目录项和目标值进行比对查出下一层所在页号再在该页下进行再次搜索直到到达叶子节点
2.2 索引的存储结构
索引中的目录项其实长得跟我们的用户记录差不多只不过目录项中的两个列是主键和页号而已所以InnoDB复用了之前存储用户记录的数据页来存储目录项为了和用户记录做一下区分我们把这些用来表示目录项的记录称为目录项记录。
页的组成结构也是一样的就是我们前边介绍过的7个部分都会为主键值生成Page Directory页目录从而在按照主键值进行查找时可以使用二分法来加快查询速度。 不论是存放用户记录的数据页还是存放目录项记录的数据页我们都把它们存放到B树这个数据结构中了所以我们也称这些数据页为节点。从图中可以看出来我们的实际用户记录其实都存放在B树的最底层的节点上这些节点也被称为叶子节点或叶节点其余用来存放目录项的节点称为非叶子节点或者内节点其中B树最上边的那个节点也称为根节点。
2.3 聚簇索引
我们上边介绍的B树本身就是一个目录或者说本身就是一个索引。它有两个特点
使用记录主键值的大小进行记录和页的排序这包括三个方面的含义 页内的记录是按照主键的大小顺序排成一个单向链表。 各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表。 存放目录项记录的页分为不同的层次在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表。
B树的叶子节点存储的是完整的用户记录。
所谓完整的用户记录就是指这个记录中存储了所有列的值包括隐藏列。
聚簇索引的优缺点
可以把相关数据保存在一起。数据访问更快。使用覆盖索引扫描的查询可以直接使用页节点中的主键值。如果表在设计和查询的时候能充分利用以上特点将会极大提高性能。当然聚簇索引也有它的缺点聚簇索引最大限度提高了I/O密集型应用的性能但如果所有的数据都存放在内存中聚簇索引就没有优势了。插入速度严重依赖插入顺序。这也是为什么InnoDB一般都会设置一个自增的int列作为主键。更新聚簇索引的代价很高因为会强制InnoDB将每个被更新的行移到新的位置。如果不安顺序插入新数据时可能会导致页分裂。二级索引可能会比想象的更大。因为在二级索引的页子节点中包含了引用行的主键列。二级索引访问可能会需要进行回表查询。
2.4 二级索引
聚簇索引是根据主键比较大小的而二级索引是通过用户建立索引的字段来比较大小的。
并且B树的叶子节点存储的并不是完整的用户记录而只是c2列主键这两个列的值。目录项记录中不再是主键页号的搭配而变成了c2列页号主键的搭配。
并且如果需要查询非索引字段的信息需要拿着主键id回去聚簇索引中查找
2.5 联合索引
在二级索引的基础采用多个字段进行比较先根据最左边的索引排一次序如果存在相同的值则根据次左边的索引字段进行比较如此类推。
3. InnoDB的B树索引的注意事项
B树的形成过程是这样的 每当为某个表创建一个B树索引聚簇索引不是人为创建的默认就有的时候都会为这个索引创建一个根节点页面。最开始表中没有数据的时候每个B树索引对应的根节点中既没有用户记录也没有目录项记录。 随后向表中插入用户记录时先把用户记录存储到这个根节点中。 当根节点中的可用空间用完时继续插入记录此时会将根节点中的所有记录复制到一个新分配的页比如页a中然后对这个新页进行页分裂的操作得到另一个新页比如页b。这时新插入的记录根据键值也就是聚簇索引中的主键值二级索引中对应的索引列的值的大小就会被分配到页a或者页b中而根节点便升级为存储目录项记录的页。
这个过程需要大家特别注意的是一个B树索引的根节点自诞生之日起便不会再移动。这样只要我们对某个表建立一个索引那么它的根节点的页号便会被记录到某个地方然后凡是InnoDB存储引擎需要用到这个索引的时候都会从那个固定的地方取出根节点的页号从而来访问这个索引。
