mysql B+树中为什么同层的非叶子节点所在的页也使用双向链表连接

mysql B+树中同层的非叶子节点所在的页也使用双向链表连接的原因：这样设计是为了提高查询效率，在查询过程中，当查询到某个非叶子节点时，需要继续向下查找。同一页中的节点被连接起来，可以缩短查找路径，从而提高查询效率。

一、mysql B+树中同层的非叶子节点所在的页也使用双向链表连接的原因

这样设计是为了提高查询效率。在查询过程中，当查询到某个非叶子节点时，需要继续向下查找。同一页中的节点被连接起来，可以缩短查找路径，从而提高查询效率。

同时，由于非叶子节点也被存储在数据页中，当需要访问某个叶子节点时，可以通过直接访问该页在内存中的地址来提高访问速度。如果没有使用双向链表连接同层级的非叶子节点，就需要进行繁琐的磁盘I/O操作，会降低访问速度。

二、mysql概述

1、简介

MySQL是一个关系型数据库管理系统，由瑞典MySQL AB 公司开发，属于 Oracle 旗下产品。MySQL 是最流行的关系型数据库管理系统之一，在 WEB 应用方面，MySQL是较好的 RDBMS (Relational Database Management System，关系数据库管理系统) 应用软件之一。

MySQL是一种关系型数据库管理系统，关系数据库将数据保存在不同的表中，而不是将所有数据放在一个大仓库内，这样就增加了速度并提高了灵活性。

MySQL所使用的 SQL 语言是用于访问数据库的最常用标准化语言。MySQL 软件采用了双授权政策，分为社区版和商业版，由于其体积小、速度快、总体拥有成本低，尤其是开放源码这一特点，一般中小型和大型网站的开发都选择 MySQL 作为网站数据库。

2、应用环境

与其他的大型数据库例如 Oracle、DB2、SQL Server等相比，MySQL自有它的不足之处，但是这丝毫也没有减少它受欢迎的程度。对于一般的个人使用者和中小型企业来说，MySQL提供的功能已经绰绰有余，而且由于 MySQL是开放源码软件，因此可以大大降低总体拥有成本。

Linux作为操作系统，Apache 或Nginx作为 Web 服务器，MySQL 作为数据库，PHP/Perl/Python作为服务器端脚本解释器。由于这四个软件都是免费或开放源码软件（FLOSS)，因此使用这种方式不用花一分钱（除开人工成本）就可以建立起一个稳定、免费的网站系统，被业界称为“LAMP“或“LNMP”组合。

3、系统特性

• MySQL使用 C和 C++编写，并使用了多种编译器进行测试，保证了源代码的可移植性。
• 支持 AIX、FreeBSD、HP-UX、Linux、Mac OS、NovellNetware、OpenBSD、OS/2 Wrap、Solaris、Windows等多种操作系统。
• 为多种编程语言提供了 API。这些编程语言包括 C、C++、Python、Java、Perl、PHP、Eiffel、Ruby、.NET和 Tcl 等。
• 支持多线程，充分利用 CPU 资源。
• 优化的 SQL查询算法，有效地提高查询速度。
• 既能够作为一个单独的应用程序应用在客户端服务器网络环境中，也能够作为一个库而嵌入到其他的软件中。
• 提供多语言支持，常见的编码如中文的 GB 2312、BIG5，日文的 Shift_JIS等都可以用作数据表名和数据列名。
• 提供 TCP/IP、ODBC 和 JDBC等多种数据库连接途径。
• 提供用于管理、检查、优化数据库操作的管理工具。
• 支持大型的数据库。可以处理拥有上千万条记录的大型数据库。
• 支持多种存储引擎。
• MySQL 是开源的，所以你不需要支付额外的费用。
• MySQL 使用标准的 SQL数据语言形式。
• MySQL 对 PHP 有很好的支持，PHP是比较流行的 Web 开发语言。
• MySQL是可以定制的，采用了 GPL协议，你可以修改源码来开发自己的 MySQL 系统。

三、双向链表简介

1、定义

双向链表(Double Linked List)是一种更复杂的链表，每个节点除了包含元素域，还包含两个链接：一个指向前一个节点，当此节点为名列前茅个节点时，指向空值；另一个指向下一个节点，当此节点为最后一个节点时，指向空值。

2、基本操作

• is_empty() 判断链表是否为空
• length 链表长度
• travel() 遍历整个链表，打印元素
• add(item) 在链表头部添加元素
• append(item) 在链表尾部添加元素
• insert(pos, item) 在指定位置插入元素
• remove(item) 删除元素
• clear() 清空链表
• is_contain(item) 判断元素是否存在

3、创建双向链表结点

实现代码：

//创建双向链表结点
Node* create_node(int data)
{
    Node* node = (Node*)malloc(sizeof(Node));//申请内存
    node->data = data;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

延伸阅读1：B+树结构定义

m阶B+树的结构定义如下：

• 每个节点非常多有m个子节点。
• 除根节点外，每个节点至少有m/2个子节点，注意如果结果除不尽，就向上取整，比如5/2=3。
• 根节点要么是空，要么是独根，否则至少有2个子节点。
• 有k个子节点的节点必有k个关键码。
• 叶节点的高度一致。