MySQL_索引树

查看树插入删除图解：

让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：域名注册、网页空间、营销软件、网站建设、尼元阳网站维护、网站推广。

时间复杂度：O(N)

时间复杂度：O(logn)

如果数据插入是递增或者递减顺序的话，会使树成为链式结构。 时间复杂度：O(N)

为了保证平衡，在插入或者删除的时候必须要旋转，通过插入或者删除性能的损失来弥补查询性能的提升。

但如果写请求和读请求一样多的时候怎么办？

随着数据的插入，树的深度会变深，树的深度越深，意味着 IO 次数越多。影响数据读取的效率。

MySQL 的页大小是16k。假设只有data 占用空间且占用 1k 一个磁盘块可以放置16条记录，三层就是 4096条记录。肯定小于 4096.

如果想要放入更多的数据的化，得加层。加层 IO 量肯定上来了。

data 太占内存，导致存储数据太少。

MySQL加载索引是以磁盘块（页）为单位的，页（Page）是 Innodb 存储引擎用于管理数据的最小磁盘单位。默认的页大小为 16KB。

假设只有 p1+key 值 占用空间且占用 10字节， 一个磁盘块可以放置1600条记录，三层就是 40960000条记录。

在B+树 上有两个头节点，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有的叶子节点（即数据节点）之间是一种链式环结构，因此可以对 B+树 进行两种查找运算：一种是对于主键的范围查找和分页查找，另一种是从根节点开始，进行随机查找。

让当前key值尽可能的少占用存储空间，才能保证存储更多的值。降低树的高度，减少IO。

保证key的长度越小越好。

彻底搞懂MySql的B+Tree

官方定义：一种能为mysql提高查询效率的数据结构，索引是为了加速对表中数据行的检索而创建的一种分散存储的数据结构。好比如，一本书，你想找到自己想看的章节内容，直接查询目录就行。这里的目录就类似索引的意思。

如上图中，如果现在有一条sql语句 select * from user where id = 40，如果没有索引的条件下，我们要找到这条记录，我们就需要在数据中进行全表扫描，匹配id = 40的数据。

如果有了索引，我们就可以通过索引进行快速查找，如上图中，可以先在索引中通过id = 40进行二分查找，再根据定位到的地址取出对应的行数据。

现在看来，索引是不是也不过如此。咋们接着往下看。

那么有的同学可能会问，既然索引缺点这么多，那我为什么还要用索引啊？也就是提高了查询速度而已。

提高了查询速度呀，这个绝对是个大优势，在数据量庞大的情况下，我们通过命中索引，能大大的提高查询速度，增删改基本消耗忽略不计。摘抄阿里P3C开发规范。

我们先来看一个sql

执行完后：

奇怪？为什么数据和我插入的顺序不一致呢，竟然给我自动排序好了！！！我们接着看

其实mysql每条数据的存储是这样子的（图自己画的，—_—,将就下）

mysql给我们提供了页的概念，并且有页目录，页目录数据为叶族节点每页的第一条数据id，页目录和每页大小均默认为16KB，如下图：

举个例子：

那么有的小伙伴可能会问，你这样也存不了多少数据呀，那假如我数据量非常多呢，这颗数怎么存呢。

以上表而言，一个id占用8个字节（long类型），name 20个字节，p指针也要占用字节的（大概4~8个字节），我们以最大8来算，那么一条数据大概就是：8+20+8=36，36个字节，那么一页换算一下是 16x1024 = 16384 个字节，那么叶子节点一页可以存储数据量为：16384/36 = 455 条数据。那么页目录又存着id，一个id8个字节，能存储16x1024/8 =2048，2048x455 = 931,840 ...粗略的算了下3层数，能存储数据量为1,908,408,320个 很多了，可能表的字段很多的话，存储数据量稍微少点，但是也很多了。

B+Tree是在B-Tree基础上的一种优化，使其更适合实现外存储索引结构，InnoDB存储引擎就是用B+Tree实现其索引结构。

这个时候有个问题思考下？为什么mysql推荐ID自增呢？这个时候是不是心里有了答案呢？或许自己可以先想想再看。

我们日常工作中，根据实际情况自行添加的索引都是辅助索引，辅助索引就是一个为了需找主键索引的二级索引，现在找到主键索引再通过主键索引找数据； （这就是所谓的回表查询）

聚簇索引就是按照每张表的主键构造一颗B+树，同时叶子节点中存放的就是整张表的行记录数据，也将聚集索引的叶子节点称为数据页。这个特性决定了索引组织表中数据也是索引的一部分，每张表只能拥有一个聚簇索引。

聚簇索引并不是一种单独的索引类型，而 是一种数据存储方式 。具体细节依赖于其实现方式。

聚簇索引的优缺点

优点：

1.数据访问更快，因为聚簇索引将索引和数据保存在同一个B+树中，因此从聚簇索引中获取数据比非聚簇索引更快

2.聚簇索引对于主键的排序查找和范围查找速度非常快 缺点：

1.插入速度严重依赖于插入顺序，按照主键的 顺序插入 是最快的方式，否则将会出现页分裂，严重影响性能。因此，对于InnoDB表，我们一般都会定义一个 自增的ID列为主键 2. 更新主键的代价很高 ，因为将会导致被更新的行移动。因此，对于InnoDB表，我们一般定义主键为不可更新。 3.二级索引访问需要两次索引查找，第一次找到主键值，第二次根据主键值找到行数据。

在 聚簇索引之上创建的索引称之为辅助索引 ，辅助索引访问数据总是需要二次查找。辅助索引叶子节点存储的不再是行的物理位置，而是主键值。通过辅助索引首先找到的是主键值，再通过主键值找到数据行的数据页，再通过数据页中的Page Directory找到数据行。

--以上可能没有说完整，或者有遗漏的地方，欢迎补充！！！

mysql如何创建二叉树

在二叉树中有一种平衡二叉树，通过平衡算法可以让二叉树两边的节点平均分布，这样就能让所有的索引查找都在一个近似的时间内完成。而MySQL这类数据库采用了二叉树的升级版B+Tree的形式，每个节点有三个支叶，不过其算法原理仍然是平衡树的原理。

网页题目：mysql树高怎么算,mysql树高度
文章出自：http://scyanting.com/article/hdpscp.html