B+Treee原理

1.数据结构
B Tree指的是平衡树。平衡树是一棵查找树，所有的叶子节点应该位于同一层。B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树（查找路径不只两个）。下面我们来看B树的规则：
（1）排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则；
（2）子节点数：非叶节点的子节点数>1，且<=M ，且M>=2，空树除外（注：M阶代表一个树节点最多有多少个查找路径，M=M路,当M=2则是2叉树,M=3则是3叉）；
（3）关键字数：枝节点的关键字数量大于等于ceil(m/2)-1个且小于等于M-1个（注：ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2);
（4）所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子;

下面我们来通过一个简单的B树的查询来认识这个结构

如上图我要从上图中找到E字母，查找流程如下
（1）获取根节点的关键字进行比较，当前根节点关键字为M，E<M（26个字母顺序），所以往找到指向左边的子节点（二分法规则，左小右大，左边放小于当前节点值的子节点、右边放大于当前节点值的子节点）；
（2）拿到关键字D和G，D<E<G 所以直接找到D和G中间的节点；
（3）拿到E和F，因为E=E 所以直接返回关键字和指针信息（如果树结构里面没有包含所要查找的节点则返回null）；

B树的插入节点流程
定义一个5阶树（平衡5路查找树;），现在我们要把3、8、31、11、23、29、50、28 这些数字构建出一个5阶树出来;

遵循规则：
（1）节点拆分规则：当前是要组成一个5路查找树，那么此时m=5,关键字数必须<=5-1（这里关键字数>4就要进行节点拆分）；
（2）排序规则：满足节点本身比左边节点大，比右边节点小的排序规则;
先插入 3、8、31、11

再插入23、29

再插入50、28

B树节点的删除流程
规则：
（1）节点合并规则：当前是要组成一个5路查找树，那么此时m=5,关键字数必须大于等于ceil（5/2）（这里关键字数<2就要进行节点合并）；
（2）满足节点本身比左边节点大，比右边节点小的排序规则;
（3）关键字数小于ceil(5/2)时先从子节点取，子节点没有符合条件时就向向父节点取，取中间值往父节点放；

B+树是B树的一个升级版，相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找。为什么说B+树查找的效率要比B树更高、更稳定；我们先看看两者的区别
规则
（1）B+跟B树不同B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子节点所能保存的关键字大大增加；
（2）B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样；
（3）B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。
（4）非叶子节点的子节点数=关键字数（来源百度百科）（根据各种资料 这里有两种算法的实现方式，另一种为非叶节点的关键字数=子节点数-1（来源维基百科)，虽然他们数据排列结构不一样，但其原理还是一样的Mysql 的B+树是用第一种方式实现）;

与红黑树的比较
红黑树等平衡树也可以用来实现索引，但是文件系统及数据库系统普遍采用 B+ Tree 作为索引结构，主要有以下两个原因：

（一）更少的查找次数

平衡树查找操作的时间复杂度和树高 h 相关，O(h)=O(logdN)，其中 d 为每个节点的出度。

红黑树的出度为 2，而 B+ Tree 的出度一般都非常大，所以红黑树的树高 h 很明显比 B+ Tree 大非常多，查找的次数也就更多。

（二）利用磁盘预读特性

为了减少磁盘 I/O 操作，磁盘往往不是严格按需读取，而是每次都会预读。预读过程中，磁盘进行顺序读取，顺序读取不需要进行磁盘寻道，并且只需要很短的磁盘旋转时间，速度会非常快。

操作系统一般将内存和磁盘分割成固定大小的块，每一块称为一页，内存与磁盘以页为单位交换数据。数据库系统将索引的一个节点的大小设置为页的大小，使得一次 I/O 就能完全载入一个节点。并且可以利用预读特性，相邻的节点也能够被预先载入。

B+Treee原理

1.数据结构
B Tree指的是平衡树。平衡树是一棵查找树，所有的叶子节点应该位于同一层。B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树（查找路径不只两个）。下面我们来看B树的规则：
（1）排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则；
（2）子节点数：非叶节点的子节点数>1，且<=M ，且M>=2，空树除外（注：M阶代表一个树节点最多有多少个查找路径，M=M路,当M=2则是2叉树,M=3则是3叉）；
（3）关键字数：枝节点的关键字数量大于等于ceil(m/2)-1个且小于等于M-1个（注：ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2);
（4）所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子;

下面我们来通过一个简单的B树的查询来认识这个结构

如上图我要从上图中找到E字母，查找流程如下
（1）获取根节点的关键字进行比较，当前根节点关键字为M，E<M（26个字母顺序），所以往找到指向左边的子节点（二分法规则，左小右大，左边放小于当前节点值的子节点、右边放大于当前节点值的子节点）；
（2）拿到关键字D和G，D<E<G 所以直接找到D和G中间的节点；
（3）拿到E和F，因为E=E 所以直接返回关键字和指针信息（如果树结构里面没有包含所要查找的节点则返回null）；

B树的插入节点流程
定义一个5阶树（平衡5路查找树;），现在我们要把3、8、31、11、23、29、50、28 这些数字构建出一个5阶树出来;

遵循规则：
（1）节点拆分规则：当前是要组成一个5路查找树，那么此时m=5,关键字数必须<=5-1（这里关键字数>4就要进行节点拆分）；
（2）排序规则：满足节点本身比左边节点大，比右边节点小的排序规则;
先插入 3、8、31、11

再插入23、29

再插入50、28

B树节点的删除流程
规则：
（1）节点合并规则：当前是要组成一个5路查找树，那么此时m=5,关键字数必须大于等于ceil（5/2）（这里关键字数<2就要进行节点合并）；
（2）满足节点本身比左边节点大，比右边节点小的排序规则;
（3）关键字数小于ceil(5/2)时先从子节点取，子节点没有符合条件时就向向父节点取，取中间值往父节点放；

B+树是B树的一个升级版，相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找。为什么说B+树查找的效率要比B树更高、更稳定；我们先看看两者的区别
规则
（1）B+跟B树不同B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子节点所能保存的关键字大大增加；
（2）B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样；
（3）B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。
（4）非叶子节点的子节点数=关键字数（来源百度百科）（根据各种资料 这里有两种算法的实现方式，另一种为非叶节点的关键字数=子节点数-1（来源维基百科)，虽然他们数据排列结构不一样，但其原理还是一样的Mysql 的B+树是用第一种方式实现）;

B+ Tree是基于B Tree和叶子节点顺序访问指针进行实现，它具有BTree的平衡性，并且通过顺序访问指针来提高区间查询的性能。
在B+ Tree中，一个节点的key从左到右非递减排列，如果某个指针的左右相邻key分别是keyi和key(i+1),且不为null,则该指针指向节点的所有key大于等于keyi且小于等于keyi+1。看下图

Problem:

Solution:

1
2
3
4
5
6
7
8
9
10
11

SELECT *
FROM
    Logs l1,
    Logs l2,
    Logs l3
WHERE
    l1.Id = l2.Id - 1
    AND l2.Id = l3.Id - 1
    AND l1.Num = l2.Num
    AND l2.Num = l3.Num
;

Problem:

Intuition:

Solution:

1
2
3
4
5
6
7
8
9
10
11

SELECT
    S1.score 'Score',
    COUNT( DISTINCT S2.score ) 'Rank'
FROM
    Scores S1
    INNER JOIN Scores S2
    ON S1.score <= S2.score
GROUP BY
    S1.id, S1.score
ORDER BY
    S1.score DESC;

Problem:

Intuition:

主要需要了解一下sql里面函数的用法。
自定义函数分为：标量值函数或表值函数两种。

标量值函数：如果 RETURNS 子句指定一种标量数据类型，则函数为标量值函数。
表值函数：如果 RETURNS 子句指定 TABLE，则函数为表值函数。
表值函数又分为两种：内嵌表值函数（行内函数）或多语句函数

如果 RETURNS 子句指定的 TABLE 不附带列的列表，则该函数为内嵌表值函数。
如果 RETURNS 子句指定的 TABLE 类型带有列及其数据类型，则该函数是多语句表值函数
如果你不晓得Returns从哪里来，请看创建函数的语法（这里是创建标量值函数的语法）：

Create function 函数名（参数）
Returns 返回值数据类型
[with {Encryption | Schemabinding }]
[as]
begin
SQL语句(必须有return 变量或值)
End
复制代码
这里的with为附加选项：

首先看一个标量值函数

1
2
3
4
5
6
7
8

CREATE FUNCTION Foo(@ret int )  --传入了一个int类型的参数
RETURNS int       --注意这里返回的是一个数据类型
AS  
BEGIN 
    declare @n int
    set @n = 3
    return @n* @ret
END

函数我们创建好了，怎么调用呢，看看下面

1

select dbo.foo(2)

结果输出为6,这里需要注意的是：创建函数的时候不需要加dbo.，但在访问的时候，标量函数要加.dbo的，否则的话会报错“不是可以识别的 内置函数名称。”

2.首先看定义一个内嵌表值函数语法：

1
2
3
4
5

create function 函数名（参数）
returns table
[with {Encryption | Schemabinding }]
as
return(一条SQL语句)

还是来看个例子比较直观:

1
2
3
4

create function GetUser(@name varchar(10))
returns table
as
return select * from userInfo where userName=@name

函数创建好了，怎么调用呢

1

select * from getuser('admin')

上面的sql将会返回一行数据，如果记录存在的话，不存在的话当然就不显示了哈。调用是不是很简单呢。

3，这里就看第三种，多语句表值函数，查看定义：
–多句表格值函数
create function 函数名（参数）
returns 表格变量名table (表格变量定义)
[with {Encryption | Schemabinding }]
as
begin
SQL语句
end
–多句表格值函数包含多条SQL语句，至少有一条在表格变量中填上数据值

我们来看个例子：

1
2
3
4
5
6
7
8

create function GetInfo(@name varchar(20))
returns @cTable table(UserName varchar(10),UserPwd varchar(10))
as
begin
　　insert into @cTable
　　select userName,userPass from userinfo where username=@name
return   --函数中最后一条语句必须是返回语句。
end

1
2

--调用
select * from GetInfo('admin')

UserName UserPwd
admin amin

对于sql的函数大体都这样了，这里我们来看个例子。

如果我们想在sql 中写一个函数，输入一个参数，返回是1到这个参数的求和值，参数当然是正整数类型的。

于是写了下面这个函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

create function sumUp(@number int)
returns int
as 
begin
    declare @sum int,@i int;
    set @sum = 0;
    set @i = 0;
    while @i <= @number
    begin
         set @sum=@sum+@i
         set @i=@i+1
     end
    return @sum
end

从1到10的求和

1

select dbo.sumUp(10)

55
从1到100的求和

1

select dbo.sumUp(100)

5050

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13

CREATE FUNCTION getNthHighestSalary ( N INT ) RETURNS INT BEGIN

SET N = N - 1;
RETURN ( 
    SELECT ( 
        SELECT DISTINCT Salary 
        FROM Employee 
        ORDER BY Salary DESC 
        LIMIT N, 1 
    ) 
);

END

Problem:

Intuition:

为了在没有查找到数据时返回 null，需要在查询结果外面再套一层 SELECT。

limit是mysql的语法

select * from table limit [m],n;

其中，m—— [m]为可选，如果填写表示skip步长，即跳过m条。

　　n——显示条数。指从第m+1条记录开始，取n条记录。
如：
select * from stu limit 2,4;
即：取stu表中第3至第6条，共4条记录。
select * from stu limit 5;
即：取stu表中前5条，共5条记录。

这一题中查找第二大的，所以是跳过一条，取一条记录，两个参数都取1.

Solution:

1
2
3
4
5

SELECT
    ( SELECT DISTINCT Salary 
     FROM Employee 
     ORDER BY Salary DESC 
     LIMIT 1, 1 ) SecondHighestSalary;

Problem:

Solution:

1
2
3
4
5

SELECT
    DepartmentId, MAX(Salary)
FROM
    Employee
GROUP BY DepartmentId;

Problem:

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#左外链接

SELECT
    C.Name AS Customers
FROM
    Customers C
    LEFT JOIN Orders O
    ON C.Id = O.CustomerId
WHERE
    O.CustomerId IS NULL;
#子查询

SELECT
    Name AS Customers
FROM
    Customers
WHERE
    Id NOT IN ( 
        SELECT CustomerId 
        FROM Orders 
    );

Problem:

Solution:

1
2
3
4
5
6
7

SELECT
    E1.NAME AS Employee
FROM
    Employee E1
    INNER JOIN Employee E2
    ON E1.ManagerId = E2.Id
    AND E1.Salary > E2.Salary;