社区公告:
    爆款云产品,限时折扣 腾讯云学生服务器10元优惠套餐 新用户千方百计送大礼,2660+元云上大礼包免费领取中! 领取宝塔管理面板3188红包! 腾讯云新客户无门槛领取2860元代金券
    发新帖

    索引原理

      [复制链接]
    306 28
    吾爱程序猿致力于打造专业优质的IT学习分享社区。站内所发布的一切文章、软件及附件信息全部来源于网络用户分享,仅限用于学习和研究目的,不得将上述内容用于商业或者非法用途。否则,一切后果请用户自负。
    本站仅提供学习分享平台,站内信息来自网络,版权争议与本站无关。您必须在下载后的24个小时之内,从您的电脑中彻底删除上述内容。如果您喜欢该程序,请支持正版,购买注册,得到更好的正版服务。
    站内所有言论纯属会员个人意见,与本论坛立场无关。严禁在本站发布政治反动、色情、暴力等不良信息和违法内容。
    吾爱程序猿作为网络平台提供者,对非法转载、盗版行为的发生不具备充分的监控能力。但是当版权拥有者提出侵权指控并出示充分的版权证明材料时,吾爱程序猿负有移除非法转载和盗版内容以及停止继续传播的义务。
    吾爱程序猿为用户免费分享产生,如果侵犯了您的权益,请及时联系右侧客服或管理员,我们将尽快处理。

    马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

    您需要 登录 才可以下载或查看,没有帐号?立即注册

    x

    想要理解索引原理必须清楚一种数据结构「平衡树」(非二叉),也就是b tree或者 b+ tree,重要的事情说三遍:“平衡树,平衡树,平衡树”。当然, 有的数据库也使用哈希桶作用索引的数据结构 , 然而, 主流的RDBMS都是把平衡树当做数据表默认的索引数据结构的。

    我们平时建表的时候都会为表加上主键, 在某些关系数据库中, 如果建表时不指定主键,数据库会拒绝建表的语句执行。 事实上, 一个加了主键的表,并不能被称之为「表」。一个没加主键的表,它的数据无序的放置在磁盘存储器上,一行一行的排列的很整齐, 跟我认知中的「表」很接近。如果给表上了主键,那么表在磁盘上的存储结构就由整齐排列的结构转变成了树状结构,也就是上面说的「平衡树」结构,换句话说,就是整个表就变成了一个索引。没错, 再说一遍, 整个表变成了一个索引,也就是所谓的「聚集索引」。 这就是为什么一个表只能有一个主键, 一个表只能有一个「聚集索引」,因为主键的作用就是把「表」的数据格式转换成「索引(平衡树)」的格式放置。

    上图就是带有主键的表(聚集索引)的结构图。图画的不是很好, 将就着看。其中树的所有结点(底部除外)的数据都是由主键字段中的数据构成,也就是通常我们指定主键的id字段。最下面部分是真正表中的数据。

    首先根据索引定位到1256这个值所在的叶结点,然后再通过叶结点取到id等于1256的数据行。 这里不讲解平衡树的运行细节, 但是从上图能看出,树一共有三层, 从根节点至叶节点只需要经过三次查找就能得到结果。如下图

    假如一张表有一亿条数据 ,需要查找其中某一条数据,按照常规逻辑, 一条一条的去匹配的话, 最坏的情况下需要匹配一亿次才能得到结果,用大O标记法就是O(n)最坏时间复杂度,这是无法接受的,而且这一亿条数据显然不能一次性读入内存供程序使用, 因此, 这一亿次匹配在不经缓存优化的情况下就是一亿次IO开销,以现在磁盘的IO能力和CPU的运算能力, 有可能需要几个月才能得出结果 。如果把这张表转换成平衡树结构(一棵非常茂盛和节点非常多的树),假设这棵树有10层,那么只需要10次IO开销就能查找到所需要的数据, 速度以指数级别提升,用大O标记法就是O(log n),n是记录总树,底数是树的分叉数,结果就是树的层次数。换言之,查找次数是以树的分叉数为底,记录总数的对数,用公式来表示就是

    用程序来表示就是Math.Log(100000000,10),100000000是记录数,10是树的分叉数(真实环境下分叉数远不止10), 结果就是查找次数,这里的结果从亿降到了个位数。因此,利用索引会使数据库查询有惊人的性能提升。

    然而, 事物都是有两面的, 索引能让数据库查询数据的速度上升, 而使写入数据的速度下降,原因很简单的, 因为平衡树这个结构必须一直维持在一个正确的状态, 增删改数据都会改变平衡树各节点中的索引数据内容,破坏树结构, 因此,在每次数据改变时, DBMS必须去重新梳理树(索引)的结构以确保它的正确,这会带来不小的性能开销,也就是为什么索引会给查询以外的操作带来副作用的原因。

    讲完聚集索引 , 接下来聊一下非聚集索引, 也就是我们平时经常提起和使用的常规索引。

    非聚集索引和聚集索引一样, 同样是采用平衡树作为索引的数据结构。索引树结构中各节点的值来自于表中的索引字段, 假如给user表的name字段加上索引 , 那么索引就是由name字段中的值构成,在数据改变时, DBMS需要一直维护索引结构的正确性。如果给表中多个字段加上索引 , 那么就会出现多个独立的索引结构,每个索引(非聚集索引)互相之间不存在关联


    举报 使用道具

    回复

    精彩评论28

    happyson10   发表于 2019-9-13 00:10:49 | 显示全部楼层
    thanks for sharing

    举报 使用道具

    回复 支持 反对
    快乐学习   发表于 2019-9-13 00:40:13 | 显示全部楼层
    我看不错噢!谢谢楼主!祝吾爱程序猿越来越好!

    举报 使用道具

    回复 支持 反对
    jesy   发表于 2019-9-13 11:10:31 | 显示全部楼层
    感谢楼主分享,祝吾爱程序猿人气高涨~

    举报 使用道具

    回复 支持 反对
    javanovice   发表于 2019-9-13 11:30:39 | 显示全部楼层
    看帖看完了至少要顶一下,楼主整理资源辛苦啦!

    举报 使用道具

    回复 支持 反对
    xelantas   发表于 2019-9-13 15:05:48 | 显示全部楼层
    看了此帖,我只想说一句吾爱程序猿很好很强大!

    举报 使用道具

    回复 支持 反对
    amoi3000   发表于 2019-9-14 07:51:37 | 显示全部楼层
    感谢楼主分享,祝吾爱程序猿人气高涨~

    举报 使用道具

    回复 支持 反对
    bawfnl   发表于 2019-9-14 09:43:01 | 显示全部楼层
    看了此帖,我只想说一句吾爱程序猿很好很强大!

    举报 使用道具

    回复 支持 反对
    MXXJ   发表于 2019-9-15 09:59:12 | 显示全部楼层
    呵呵。。。。。回帖一个

    举报 使用道具

    回复 支持 反对
    bawfnl   发表于 2019-9-16 11:08:23 | 显示全部楼层
    看了此帖,我只想说一句吾爱程序猿很好很强大!

    举报 使用道具

    回复 支持 反对
    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则


    【新用户限量秒杀】热门云产品限量秒杀,云服务器1核1G 首年99元

    快速回复 返回顶部 返回列表