mysql 索引 b树 b+树区别_哈希值是唯一的吗

【mysql】深入理解Mysql索引底层数据结构与算法　　索引数据结构：红黑树、Hash、B+树　　索引的本质　　索引是帮助MySQL高效数据的排好序的数据结构　　数据结构网站　　https://www.cs.usfca.edu/~galles/visualization/Algorithms.html 　　索引的数据结构　　层层递进理解最终的B+树：二叉树->红黑树->B树->B+树　　

　　二叉树　　MySQL索引底层并未使用单边增长的倾斜问题，变相为链表，查找效率低，与全表扫描差别不大　　RBTree-红黑树　　可参考【并发专题-HashMap】中红黑树索引底层也未使用大数据量情况下，高度不可控　　B Tree B树-平衡多路查找树　　

　　所有节点存储：索引+数据特点：叶节点具有相同的深度，叶节点的指针为空所有索引素不重复节点中的数据索引从左到右递增排列　　B+Tree 索引　　

　　MySQL索引没有用B Tree，而是用B+Tree——B树的变种，有比B树更高的查询效率　　其对B树进行改造，数据全部存叶子节点：非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引非叶子节点从叶子节点取中间某些索引，冗余存储叶子节点包含所有索引字段，且数据索引从左到右递增排列叶子节点用双向指针连接，提高区间访问的性能叶子节点间，可变相理解是双向链表指针：存储节点在磁盘的位置——自己的和前面节点的，见上图　　索引的升级–树平衡过程　　当节点插满数据之后，节点第一个索引（即最小的一个素）作为冗余索引上升到上一节点，在此基础上做树的平衡　　千万级数据表如何用B+树快速查找　　查找时比较费时的步骤是load节点到内存，而在内存查找数据是比较快的对于MySQL来说，每个（页）节点（root）分配的空间是16kb，高度为3的B+树整体可存储两千多万数据：非叶子页节点可存储的数据量：16kb/（索引数据（一般占据8字节）+指针（6个字节））约等于1170叶子节点可存储的数据量：（有data，所以比非叶子节点少）16kb/（索引+指针+数据）1kb（一般一行数据不会超过1kb）=16整体可存储数据个数：（高度为3）1170 * 1170 * 16两千多万条记录因此，高度为3的B+树中，查找某一个素，只经过3次磁盘IO即可找到B+树的结构，决定了即使是千万级数据表，仍可快速查找到素　　B树与B+树区别　　区别B+树叶子节点之间多了双向指针，方便区间范围查找B+树非叶子节点只存储索引，这样一个节点能存放更多索引，存放相同数量的索引，B+树的高度会更小　　引：为什么MySQL选择B+树做索引？　　树的高度，影响索引查找效率B+树将data放到叶子节点，而非叶子节点只存储索引，存放同样数量的索引，其高度更小，查找效率更高　　hash索引　　对索引的key进行一次hash计算就可以定位出数据存储的位置很多时候Hash索引要比B+ 树索引更高效仅能满足 “=”，“IN”，不支持范围查询hash冲突问题　　

　　存储引擎索引实现　　存储引擎是表级别生效的　　聚集索引&聚簇索引&稀疏索引　　聚集索引也叫聚簇索引叶节点包含完整的数据记录非聚簇索引索引文件和数据文件是分离的稀疏索引非聚簇索引的一种　　引：聚集索引和非聚集索引哪个效率更高？　　聚集索引更高，索引和数据在一起，不经过跨文件查找数据　　MyISAM存储引擎　　非聚集索引索引文件和数据文件是分离的表存储在磁盘中，3个文件.frm表结构.MYD数据.MYI索引主键索引和非主键索引（辅助/二级索引）结构相同，如下：　　

　　查找数据过程　　如找15，参见上图：层层递进：根节点15->15->15-data（0x07 索引所在磁盘文件地址）->磁盘中MYI文件，定位索引对应的数据行->MYD文件中数据　　InnoDB存储引擎　　表数据文件本身就是按B+Tree组织的一个索引结构文件聚集索引叶节点包含完整的数据记录建议InnoDB表必须建主键，且推荐使用整型的自增主键非主键索引结构叶子节点存储的是主键值因：一致性和节省存储空间表存储在磁盘中，2个文件.frm表结构.ibd索引和数据主键索引和非主键索引（辅助/二级索引）结构不同，如下图：非主键索引查找，可能涉及回表操作第一次搜索非主键索引的B+Tree 拿到主键值后再去搜索主键索引的 B+Tree，这个过程就是所谓的回表非主键索引不一定必须回表如果查询的列本身就存在于索引中，那么即使使用二级索引，一样也是不需要回表　　

　　查找数据过程　　如找15，参见上图：层层递进：根节点15->15->15-data（15所在行的整行数据都存储）　　为什么InnoDB表必须建主键，且推荐使用整型的自增主键索引　　为什么InnoDB表必须建立主键？如果不建立主键会从第一列开始，选择所有素都不相等的一列作为索引，来组织B+树如果选不到所有素都不相同的列，则会创建隐藏列作为索引，组织B+树浪费MySQL资源和性能为什么推荐使用整型自增主键做索引？整型：在索引定位的过程中，中间经历过多次数据比较大小整型查找过程中值比较效率高字符串会按ASCII码，逐个字符比较，又经历多次，效率低整型数据占用的磁盘空间小，节约空间自增：自增主键与索引有序的特性相吻合(索引插入时，按从左至右递增向后插入即可)，在新增主键时一般不会导致叶子节点频繁分裂以及平衡，效率高如果非自增，若在节点中间硬插入数据，则该节点分裂，B+树还要进行平衡操作，效率低　　联合索引底层数据结构　　概念　　指的是对一张表上的多个列进行索引即：表上多个列加起来组成一个索引供快速查询使用一般不建议单表建立过多单值索引，而是建立2-3个联合索引来满足查询需要分类联合主键索引联合非主键索引（不常用）查询一行数据，当单列和索引和联合索引发生冲突时，MySQL优先选择单列索引　　底层数据结构　　按索引建立先后顺序，维护存储，仍是B+树结构查找也按先后顺序逐个匹配查找，引出最左前缀原则/原理　　

　　优势/好处　　当两个或多个列的组合是唯一值时，联合索引是个不错的选择可以对后续多个键值进行排序减少开销每多一个索引，都会增加写操作的开销和磁盘空间的开销。对于大量数据的表，使用联合索引会大大的减少开销效率高索引列越多，通过索引筛选出的数据越少　　最左前缀/左列原理（原则）　　MySQL建立联合索引时会遵循最左前缀匹配的原则，即最左优先，在检索数据时从联合索引的最左边开始匹配最左前缀原则规定了联合索引在何种查询中才能生效，规则如下：如果想使用联合索引，联合索引的最左边的列必须作为过滤条件，否则联合索引不会生效【补充说明】最左前缀匹配原则：mysql会一直向右匹配直到遇到范围查询(>、<、between、like)就停止匹配=和in可以乱序，比如a = 1 and b = 2 and c = 3 建立(a,b,c)索引可以任意顺序，mysql的查询优化器会优化成索引可以识别的形式　　联合索引为什么采用最左前缀原则？　　由索引的底层数据结构决定其时从左至右排好序的B+树

mysql 索引 b树 b+树区别_哈希值是唯一的吗

相关推荐