网站开发专业前景,私密浏览器免费版在线看,深圳建网站企业,vi设计的基本要素索引实现原理
索引#xff1a;排好序的数据结构 优点#xff1a;降低I/O成本#xff0c;CPU的资源消耗#xff08;数据持久化在磁盘中#xff0c;每次查询都得与磁盘交互#xff09; 缺点#xff1a;更新表效率变慢#xff0c;#xff08;更新表数据#xff0c;还要…索引实现原理
索引排好序的数据结构 优点降低I/O成本CPU的资源消耗数据持久化在磁盘中每次查询都得与磁盘交互 缺点更新表效率变慢更新表数据还要更新索引占用空间 分类主键索引唯一索引单值索引组合索引
索引的数据结构
Hash表舍弃不适合范围查找和排序
hash 是一维数组 二维链表取模后进行存储
对于hash算法的CRUD来讲时间复杂度为O(1) 但对于范围查询和排序来讲时间复杂度又从最好变为O(n) 二叉树舍弃:自增序列无效
理想情况
mysql不使用的原因对于自增数据树左倾或右倾形成链表时间复杂度变回了O(n)
红黑树舍弃:树会很高
本质就是二叉树相比较于二叉树他有平衡功能(当一边高时会自动更新根节点)又称为二叉平衡树
mysql 不使用原因数据量大的时候树会更高查找到叶子节点效率也会慢每层就是一次IO
B Tree舍弃每个节点存放数据可以优化
特点在每个节点放多个索引 优点树就不会高但每个节点都会存data数据会占据很大的磁盘空间
B Treemysql默认
优点 1.非叶子节点不储data,只存储索引可以放更多的索引 2.叶子节点包含所有索引data字段由双向链表排成一行更好的实现范围查找和排序 3.叶子节点用指针连接提高区间访问的性能
mysql 默认每个节点为16KB, 例如若使用bigInt的主键每个节点大概可放1170 个索引若树高3层则为1170*1170 *16 约为2000多万索引 总结(数据存叶子节点双向链表)
BTree 和BTree都是多路搜索树区别在于叶子节点和非叶子节点的处理。 1.BTree 每个节点都储存索引数据BTree 的非叶子节点只存储索引指向叶子节点的指针数据存到叶子节点这样BTree 的非叶子节点就可以放更多的索引树的层级也就降低了这样查找更快,减少了磁盘IO。 2.BTree 的叶子节点都有指针相连接形成双向链接表这样在范围和排序时更快而BTree 的叶子节点没有相连接范围查找时还得向父节点查找。所以BTree 的范围查找和排序更好
数据结构训练网址
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
