原文出处：聊一聊字节跳动的面试

一、算法题

一面：

1.  lc 里最长上升子序列的变形题  
2. 实现输入英文单词联想的功能

二面：

1.矩阵旋转，要求空间复杂度 O(1)
2.无序的数组的中位数。要求时间复杂度尽可能的小

二、计算机网络

1. tcp 怎么保证数据包有序

  1. 主机每次发送数据时，TCP 就给每个数据包分配一个序列号并且在一个特定的时间内等待接收主机对分配的这个序列号进行确认。

  2. 如果发送主机在一个特定时间内没有收到接收主机的确认，则发送主机会重传此数据包。

  3. 接收主机利用序列号对接收的数据进行确认，以便检测对方发送的数据是否有丢失或者乱序等。

  4. 接收主机一旦收到已经顺序化的数据，它就将这些数据按正确的顺序重组成数据流并传递到高层进行处理。

2. tcp 和 udp 的异同

TCP 是面向流的可靠数据传输连接
UDP 是面向数据包的不可靠无连接

3. tcp 怎么保证可靠性

差错检验机制，反馈机制，重传机制，引入序号，滑动窗口协议，选择重传

4. tcp 中拥塞避免和流量控制机制

拥塞避免和流量控制这两种机制很像，但是流量控制是由接收方的接受能力也就是接收窗口所决定的，如果接收窗口够大，以动态调整发送窗口的大小调整发送速度
拥塞避免主要由网络情况所限制，网络情况良好，则加大发送速率，网络状态差（冗余 ACK 和丢包）则降低发送速率（慢启动，拥塞控制，快恢复，快重传） RENO，BBR

5. tcp 四次挥手的详细解释

tcp 四次挥手其实可以分为两个阶段
第一：
客户端至服务器的半双工连接关闭
客户端向服务器发送 FIN 信号，进入 FIN_WAIT1 的状态，等待服务器的 ACK 信号
收到服务器的 ACK 后，进入 FIN_WAIT2
第二：
服务器至客户端的半双工连接关闭
客户端收到服务器发来的 FIN 后，发送 ACK，并进入 TIME_WAIT，等待 2msl，若无异常，则客户端认为连接成功关闭
服务器收到客户端发来的 ACK 后，关闭连接

6. 四次挥手之后为什么还要等待 2msl

MSL 是报文最大生存时间
1 是因为有可能客户端发往服务器的 ACK 丢失，服务器并不知道客户端已经确认关闭，这时候客户端的关闭会导致服务器端无法正常关闭
2 是为了保证连接中的报文都已经传递。假如短时间关闭又重新实现一个 TCP 还连到了同个端口上，旧连接中尚未消失的数据就会被认为是新连接的数据。

7. 浏览器从输入网址到显示出网页的全过程

1. 输入网址或者 ip。
2. 如果输入的是网址，首先要查找域名的 ip 地址
第一步会在浏览器缓存中查找，如果没有，转至查询系统缓存，如果还是没有，发送请求给路由器，路由器首先会在自身的缓存中查找，如果还是没有，向 ips发出请求，查询 ips 中的 dns 缓存，如果还是没有递归向上查询直至根服务器。
3. 浏览器与 ip 机器之间建立 TCP 连接（三次握手）（HTTP）或者在 TCP 上进一步建立 SSL/TLS 连接 （HTTPS）
接下来就是发送 HTTP 报文啥的了
GET，POST，DELETE，PUT。

8. 滑动窗口机制的原理和理解

GBN 协议，回退 N 步协议，这是对停等协议的改进，因为停等协议的传输效率非常低下。每次可发送的数据为 N，基数为 base，小于 base 的数据已经发送并且确认，base 是最小的已发送未确认的报文序号。在接收端同样也有一个接收窗口，（解释）GBN采用的是累计确认方式，这时候说一下选择重传机制。再说一下 TCP 中既不是 GBN 也不是 SR ，而是 GBN 和 SR 的综合体。
N 的大小必须报文序列编号的一半，否则接收端对报文的确认可能发生混淆

9. Https 原理和实现

10. cookie 和 session 的区别是什么

由于 HTTP 协议是无状态的协议，所以服务端需要记录用户的状态时，就需要用某种机制来识具体的用户
cookie 存在本地的上的
session 是存在服务器上的
通俗讲，Cookie 是访问某些网站以后在本地存储的一些网站相关的信息，下次再访问的时候减少一些步骤。另外一个更准确的说法是：Cookies 是服务器在本地机器上存储的小段文本并随每一个请求发送至同一个服务器，是一种在客户端保持状态的方案。
Session 是存在服务器的一种用来存放用户数据的类HashTable结构。
二者都用来保持用户的状态，cookie可更改，对服务器来说并不安全，服务器常见做法有这两种：
1.把 session 加密后放入浏览器的 cookie 中，浏览器重连后将加密的 session 发给服务器
2.cookie 中存储着 session的id，浏览器重连时只需要发送 session_id' 即可

三、操作系统

1. 进程和线程的区别

进程就是保存上下文切换的程序执行时间总和 = CPU 加载上下文 + CPU 执行 + CPU 保存上下文

2. 线程是什么呢？

进程的颗粒度太大，每次都要有上下的调入，保存，调出。如果我们把进程比喻为一个运行在电脑上的软件，那么一个软件的执行不可能是一条逻辑执行的，必定有多个分支和多个程序段，就好比要实现程序A，实际分成 a，b，c 等多个块组合而成。那么这里具体的执行就可能变成：
程序 A 得到 CPU =》CPU 加载上下文，开始执行程序 A 的 a 小段，然后执行 A 的 b 小段，然后再执行 A 的 c 小段，最后 CPU 保存 A 的上下文。
这里 a，b，c 的执行是共享了 A 的上下文， CPU 在执行的时候没有进行上下文切换的。这里的 a，b，c就是线程，也就是说线程是共享了进程的上下文环境，的更为细小的 CPU 时间段。

3. 进程切换与线程切换

4. Linux 中五种 IO 模型

1) 阻塞 I/O（blocking I/O）
2) 非阻塞 I/O （nonblocking I/O）
3) I/O 复用 (select 和poll) （I/O multiplexing）
4) 信号驱动 I/O （signal driven I/O (SIGIO)）
5) 异步 I/O （asynchronous I/O (the POSIX aio_functions)）
前四种都是同步，只有最后一种才是异步 IO。
同步 IO 和异步 IO 的区别就在于：数据拷贝的时候进程是否阻塞！
阻塞 IO 和非阻塞 IO 的区别就在于：应用程序的调用是否立即返回！

5. 如何实现一个同步非阻塞的请求

6. 实现进程同步的机制有什么

7. 信号量的实现机制

8. 共享锁和排他锁

9. 实现一个读写锁

10. 设计一个无锁队列

11. 协程的原理

四、数据库

1. 索引是什么

索引 （Index） 是帮助 MySQL 高效获取数据的数据结构。

  1. 索引能极大的减少存储引擎需要扫描的数据量

  2. 索引可以把随机 IO 变成顺序 IO

  3. 索引可以帮助我们在进行 分组、 排序等操作时，避免使用临时表

2. 为什么要用 B+ 树（B+ 树的优缺点）

B+ 树是 B- 树的变种 （PLUS 版）多路绝对平衡查找树，好的时间复杂度
B+ 树扫库、表能力更强
B+ 树的磁盘读写能力更强
B+ 树的排序能力更强
B+ 树的查询效率更加稳定（仁者见仁、智者见智，有可能 B-Tree 第一次就命中了，直接返回，而 B+Tree 需要找到叶节点，所以查找效率不一定比 B-Tree 更高）
支持顺序排序，叶节点之间存在链接

3. B+索引和哈希索引的区别？

B-tree 索引
索引是按照顺序存储的，所以，如果按照 B-tree 索引，可以直接返回，带顺序的数据，但这个数据只是该索引列含有的信息。因此是顺序 I/O
适用于：
精确匹配
范围匹配
最左匹配
Hash 索引
索引列值的哈希值+数据行指针：因此找到后还需要根据指针去找数据，造成随机I/O
适合：
精确匹配
不适合：
模糊匹配
范围匹配
不能排序
1、hash 索引仅满足 “=”、“IN” 和 “<=>” 查询，不能使用范围查询因为 hash 索引比较的是经常 hash 运算之后的hash值，因此只能进行等值的过滤，不能基于范围的查找，因为经过hash算法处理后的 hash 值的大小关系，并不能保证与处理前的 hash 大小关系对应。
2、hash 索引无法被用来进行数据的排序操作由于 hash 索引中存放的都是经过hash 计算之后的值，而 hash 值的大小关系不一定与 hash 计算之前的值一样，所以数据库无法利用 hash 索引中的值进行排序操作。
3、对于组合索引，Hash 索引在计算 Hash 值的时候是组合索引键合并后再一起计算 Hash 值，而不是单独计算 Hash 值，所以通过组合索引的前面一个或几个索引键进行查询的时候，Hash 索引也无法被利用。
4、Hash 索引遇到大量Hash值相等的情况后性能并不一定就会比 B-Tree 索引高。对于选择性比较低的索引键，如果创建 Hash 索引，那么将会存在大量记录指针信息存于同一个 Hash 值相关联。这样要定位某一条记录时就会非常麻烦，会浪费多次表数据的访问，而造成整体性能低下。
总结：哈希适用在小范围的精确查找，在列数据很大，又不需要排序，不需要模糊查询，范围查询时有用

4. B+ 树中叶子节点间的指针有什么用？

使得访问更加简单，b 树的话需要不断在父节点和叶子节点之间来回移动

5. 聚簇和非聚簇索引的区别？

聚簇索引：将数据存储与索引放到了一块，找到索引也就找到了数据，聚簇索引的叶子节点就是数据节点，由于聚簇索引是将数据跟索引结构放到一块，因此一个表仅有一个聚簇索引，聚簇索引具有唯一性
非聚簇索引：非聚簇索引的叶子节点仍然是索引节点，只不过有指向对应数据块的指针。将数据存储于索引分开结构，索引结构的叶子节点指向了数据的对应行

6. 非聚簇索引的查询都要回表吗？

是的

7. B+ 树和 AVL 树 B 树二叉搜索树有什么区别？

这几种各有交集但又不尽相同。
什么是二叉搜索树？
它或者是一棵空树，或者是具有下列性质的二叉树：
1.左子节点的值必定小于父节点的值
2.右子节点的值必定大于父节点的值
首先 AVL 树是自平衡的二叉搜索树AVL在该定义的基础上加入了平衡条件，即：某节点的左右子树的高度差小于等于1
另一种非严格自平衡的二叉搜索树是红黑树，二者使用场景略微有些不同。
AVL 追求整体的绝对平衡，适合于少量插入，大量查找的应用场景（因为维护全局平衡，插入一个往往需要 O(log n)）
红黑树适用于一部分插入，一部分查询的场景（变色，左旋右旋场景相对少些）
B+ 树是对 B 树的拓展
一棵 m 阶 B 树 (balanced tree of order m) 是一棵平衡的m路搜索树。它或者是空树，或者是满足下列性质的树：
1、根结点至少有两个子女；
2、每个非根节点所包含的关键字个数 j 满足：┌m/2┐ - 1 <= j <= m - 1；
3、除根结点以外的所有结点（不包括叶子结点）的度数正好是关键字总数加 1，故内部子树个数 k 满足：┌m/2┐ <= k <= m ；
4、所有的叶子结点都位于同一层。
B+ 树对 B 树的改进就是：只有叶节点存数据，并且维护了两个指针，一个指向根节点另一个指向顺序叶节点的首位。
B+ 树还在叶子节点中加入了链接指针

五、杂项

这一部分和项目比较相关。基本上项目中有什么或者面试官想到什么问什么，问了很多但是不通用。就只写一点。

1. GIL 是什么

全局状态锁

2. 为什么会有?

出现多线程编程之间数据和状态一致性问题，为了解决这个数据不能同步的问题

3. 有什么作用?

4. 怎么规避它对于并行的影响?

六、语言相关

1. Python 的内存管理机制

（1）垃圾回收
（2）引用计数
（3）内存池机制

2. 讲一下 Python GC 的原理和详细解释（分代，标记回收，内存划分）

Python 语言默认采用的垃圾收集机制是『引用计数法 Reference Counting』，『引用计数法』的原理是：每个对象维护一个 ob_ref 字段，用来记录该对象当前被引用的次数，每当新的引用指向该对象时，它的引用计数 ob_ref 加 1，每当该对象的引用失效时计数 ob_ref 减 1，一旦对象的引用计数为 0，该对象立即被回收，对象占用的内存空间将被释放。
为了解决对象的循环引用问题，Python 引入了标记-清除和分代回收两种 GC 机制。
标记就是使用有向图的方式，不可达的清除掉（主要用来清理容器对象）
分代分为三代：年轻，中年，老年。年轻对象满，触发 GC，可回收对象回收掉，不可回收移到中年中去，以此类推。结合标记使用
引用计数增加
1.对象被创建： x=4
2.另外的别人被创建： y=x
3.被作为参数传递给函数： foo(x)
4.作为容器对象的一个元素： a=[1,x,'33']
引用计数减少
1.一个本地引用离开了它的作用域。比如上面的 foo(x) 函数结束时，x指向的对象引用减 1。
2.对象的别名被显式的销毁： del x ；或者 del y
3.对象的一个别名被赋值给其他对象： x=789
4.对象从一个窗口对象中移除： myList.remove(x)
5.窗口对象本身被销毁： del myList，或者窗口对象本身离开了作用域。
垃圾回收
1、当内存中有不再使用的部分时，垃圾收集器就会把他们清理掉。它会去检查那些引用计数为 0 的对象，然后清除其在内存的空间。当然除了引用计数为0的会被清除，还有一种情况也会被垃圾收集器清掉：当两个对象相互引用时，他们本身其他的引用已经为 0 了。
2、垃圾回收机制还有一个循环垃圾回收器, 确保释放循环引用对象 ( a 引用 b, b 引用 a, 导致其引用计数永远不为 0)。

3. Python 中 static_method 、 class_mathod 、和普通 method 有什么区别

4. 迭代器和生成器有什么区别？

先说结论，生成器式 一种特殊的迭代器：其在使用时生成。
首先明确两个概念：
Iterable ：所有实现了 iter 的对象均可称作 Iterablec。Iterator：是指同时实现了 iter__ 和 _next 的对象，迭代器也属于 Iterable。

小结
凡是可作用于 for 循环的对象都是 Iterable 类型；
凡是可作用于 next() 函数的对象都是 Iterator 类型，它们表示一个惰性计算的序列

5. 生成器怎么使用？

两种方式：

a =(i for i in range(100))  
def a(n):  
    i = 0  
    while(i < n):  
       yield i  
       i += 1

原文出处：再有人问你为什么MySQL用B+树做索引，就把这篇文章发给她

索引这个词，相信大多数人已经相当熟悉了，很多人都知道MySQL的索引主要以B+树为主，但是要问到为什么用B+树，恐怕很少有人能把前因后果讲述的很完整。本文就来从头到尾介绍下数据库的索引。

索引是一种数据结构，用于帮助我们在大量数据中快速定位到我们想要查找的数据。** 索引最形象的比喻就是图书的目录了。注意这里的大量，数据量大了索引才显得有意义，如果我想要在[1,2,3,4]中找到4这个数据，直接对全数据检索也很快，没有必要费力气建索引再去查找。索引在mysql数据库中分三类：

B+树索引、Hash索引、全文索引

我们今天要介绍的是工作开发中最常接触到innodb存储引擎中的的B+树索引。

要介绍B+树索引，就不得不提二叉查找树，平衡二叉树和B树这三种数据结构。B+树就是从他们仨演化来的。

二叉查找树

首先，让我们先看一张图



从图中可以看到，我们为user表（用户信息表）建立了一个二叉查找树的索引。图中的圆为二叉查找树的节点，节点中存储了键(key)和数据(data)。

键对应user表中的id，数据对应user表中的行数据。二叉查找树的特点就是任何节点的左子节点的键值都小于当前节点的键值，右子节点的键值都大于当前节点的键值。** 顶端的节点我们称为根节点，没有子节点的节点我们称之为叶节点。

如果我们需要查找id=12的用户信息，利用我们创建的二叉查找树索引，查找流程如下：

利用二叉查找树我们只需要3次即可找到匹配的数据。如果在表中一条条的查找的话，我们需要6次才能找到。

平衡二叉树

上面我们讲解了利用二叉查找树可以快速的找到数据。但是，如果上面的二叉查找树是这样的构造：



这个时候可以看到我们的二叉查找树变成了一个链表。

如果我们需要查找id=17的用户信息，我们需要查找7次，也就相当于全表扫描了。

导致这个现象的原因其实是二叉查找树变得不平衡了，也就是高度太高了，从而导致查找效率的不稳定。

为了解决这个问题，我们需要保证二叉查找树一直保持平衡**，就需要用到平衡二叉树了。

平衡二叉树又称AVL树，在满足二叉查找树特性的基础上，要求每个节点的左右子树的高度差不能超过1。

下面是平衡二叉树和非平衡二叉树的对比：



由平衡二叉树的构造我们可以发现第一张图中的二叉树其实就是一棵平衡二叉树。

平衡二叉树保证了树的构造是平衡的，当我们插入或删除数据导致不满足平衡二叉树不平衡时，平衡二叉树会进行调整树上的节点来保持平衡。具体的调整方式这里就不介绍了。

平衡二叉树相比于二叉查找树来说，查找效率更稳定，总体的查找速度也更快。

B树

因为内存的易失性。一般情况下，我们都会选择将user表中的数据和索引存储在磁盘这种外围设备中。

但是和内存相比，从磁盘中读取数据的速度会慢上百倍千倍甚至万倍，所以，我们应当尽量减少从磁盘中读取数据的次数。 另外，从磁盘中读取数据时，都是按照磁盘块来读取的，并不是一条一条的读。**

如果我们能把尽量多的数据放进磁盘块中，那一次磁盘读取操作就会读取更多数据，那我们查找数据的时间也会大幅度降低。

如果我们用树这种数据结构作为索引的数据结构，那我们每查找一次数据就需要从磁盘中读取一个节点，也就是我们说的一个磁盘块，我们都知道平衡二叉树可是每个节点只存储一个键值和数据的。

那说明什么？

说明每个磁盘块仅仅存储一个键值和数据！

那如果我们要存储海量的数据呢？

可以想象到二叉树的节点将会非常多，高度也会及其高，我们查找数据时也会进行很多次磁盘IO，我们查找数据的效率将会极低！



为了解决平衡二叉树的这个弊端，我们应该寻找一种单个节点可以存储多个键值和数据的平衡树。也就是我们接下来要说的B树。

B树（Balance Tree）即为平衡树的意思，下图即是一颗B树。



图中的p节点为指向子节点的指针，二叉查找树和平衡二叉树其实也有，因为图的美观性，被省略了。-图中的每个节点称为页，页就是我们上面说的磁盘块，在mysql中数据读取的基本单位都是页，所以我们这里叫做页更符合mysql中索引的底层数据结构。

从上图可以看出，B树相对于平衡二叉树，每个节点存储了更多的键值(key)和数据(data)，并且每个节点拥有更多的子节点，子节点的个数一般称为阶，上述图中的B树为3阶B树，高度也会很低。

基于这个特性，B树查找数据读取磁盘的次数将会很少，数据的查找效率也会比平衡二叉树高很多。

假如我们要查找id=28的用户信息，那么我们在上图B树中查找的流程如下：

B+树

B+树是对B树的进一步优化。让我们先来看下B+树的结构图：



根据上图我们来看下B+树和B树有什么不同。

1. B+树非叶子节点上是不存储数据的，仅存储键值，而B树节点中不仅存储键值，也会存储数据。之所以这么做是因为在数据库中页的大小是固定的，innodb中页的默认大小是16KB。如果不存储数据，那么就会存储更多的键值，相应的树的阶数（节点的子节点树）就会更大，树就会更矮更胖，如此一来我们查找数据进行磁盘的IO次数有会再次减少，数据查询的效率也会更快。另外，B+树的阶数是等于键值的数量的，如果我们的B+树一个节点可以存储1000个键值，那么3层B+树可以存储1000×1000×1000=10亿个数据。一般根节点是常驻内存的，所以一般我们查找10亿数据，只需要2次磁盘IO。

2. 因为B+树索引的所有数据均存储在叶子节点，而且数据是按照顺序排列的。那么B+树使得范围查找，排序查找，分组查找以及去重查找变得异常简单。而B树因为数据分散在各个节点，要实现这一点是很不容易的。 有心的读者可能还发现上图B+树中各个页之间是通过双向链表连接的，叶子节点中的数据是通过单向链表连接的。其实上面的B树我们也可以对各个节点加上链表。其实这些不是它们之前的区别，是因为在mysql的innodb存储引擎中，索引就是这样存储的。也就是说上图中的B+树索引就是innodb中B+树索引真正的实现方式，准确的说应该是聚集索引（聚集索引和非聚集索引下面会讲到）。

通过上图可以看到，在innodb中，我们通过数据页之间通过双向链表连接以及叶子节点中数据之间通过单向链表连接的方式可以找到表中所有的数据。

MyISAM中的B+树索引实现与innodb中的略有不同。在MyISAM中，B+树索引的叶子节点并不存储数据，而是存储数据的文件地址。

聚集索引 VS 非聚集索引

在上节介绍B+树索引的时候，我们提到了图中的索引其实是聚集索引的实现方式。那什么是聚集索引呢？在MySQL中，B+树索引按照存储方式的不同分为聚集索引和非聚集索引。这里我们着重介绍innodb中的聚集索引和非聚集索引。

1. 聚集索引（聚簇索引）：以innodb作为存储引擎的表，表中的数据都会有一个主键，即使你不创建主键，系统也会帮你创建一个隐式的主键。这是因为innodb是把数据存放在B+树中的，而B+树的键值就是主键，在B+树的叶子节点中，存储了表中所有的数据。这种以主键作为B+树索引的键值而构建的B+树索引，我们称之为聚集索引。

2. 非聚集索引（非聚簇索引）：以主键以外的列值作为键值构建的B+树索引，我们称之为非聚集索引。非聚集索引与聚集索引的区别在于非聚集索引的叶子节点不存储表中的数据，而是存储该列对应的主键，想要查找数据我们还需要根据主键再去聚集索引中进行查找，这个再根据聚集索引查找数据的过程，我们称为回表。

明白了聚集索引和非聚集索引的定义，我们应该明白这样一句话：数据即索引，索引即数据。

利用聚集索引和非聚集索引查找数据

前面我们讲解B+树索引的时候并没有去说怎么在B+树中进行数据的查找，主要就是因为还没有引出聚集索引和非聚集索引的概念。下面我们通过讲解如何通过聚集索引以及非 聚集索引查找数据表中数据的方式介绍一下B+树索引查找数据方法。

利用聚集索引查找数据



还是这张B+树索引图，现在我们应该知道这就是聚集索引，表中的数据存储在其中。现在假设我们要查找id>=18并且id<40的用户数据。对应的sql语句为select * from user where id>=18 and id <40，其中id为主键。具体的查找过程如下：

从内存中读取到页1，要查找这个id>=18 and id <40或者范围值，我们首先需要找到id=18的键值。

从页1中我们可以找到键值18，此时我们需要根据指针p2，定位到页3。

从磁盘中读取页3后将页3放入内存中，然后进行查找，我们可以找到键值18，然后再拿到页3中的指针p1，定位到页8。

将页8读取到内存中后。

因为页中的数据是链表进行连接的，而且键值是按照顺序存放的，此时可以根据二分查找法定位到键值18。

此时因为已经到数据页了，此时我们已经找到一条满足条件的数据了，就是键值18对应的数据。

因为是范围查找，而且此时所有的数据又都存在叶子节点，并且是有序排列的，那么我们就可以对页8中的键值依次进行遍历查找并匹配满足条件的数据。

我们可以一直找到键值为22的数据，然后页8中就没有数据了，此时我们需要拿着页8中的p指针去读取页9中的数据。

那么查找到此终止。

最终我们找到满足条件的所有数据为：

(18,kl),(19,kl),(22,hj),(24,io),(25,vg),(29,jk),(31,jk),(33,rt),(34,ty),(35,yu),(37,rt),(39,rt)。

总共12条记录。

下面看下具体的查找流程图：



利用非聚集索引查找数据

读者看到这张图的时候可能会蒙，这是啥东西啊？怎么都是数字。如果有这种感觉，请仔细看下图中红字的解释。什么？还看不懂？那我再来解释下吧。首先，这个非聚集索引表 示的是用户幸运数字的索引（为什么是幸运数字？一时兴起想起来的:-)），此时表结构是这样的。

idnameluckyNum
1zs23
2ls7

在叶子节点中，不在存储所有的数据了，存储的是键值和主键。对于叶子节点中的x-y，比如1-1。左边的1表示的是索引的键值，右边的1表示的是主键值。如果我们要找到幸运数字为33的用户信息，对应的sql语句为select * from user where luckNum=33。查找的流程跟聚集索引一样，这里就不详细介绍了。我们最终会找到主键值47，找到主键后我们需要再到聚集索引中查找具体对应的数据信息，此时又回到了聚集索引的查找流程。 下面看下具体的查找流程图：

在MyISAM中，聚集索引和非聚集索引的叶子节点都会存储数据的文件地址。

总结

本篇文从二叉查找树，详细说明了为什么mysql用B+树作为数据的索引，以及在innodb中数据库如何通过B+树索引来存储数据以及查找数据。我们一定要记住这句话：数据即索引，索引即数据。