MySQL数据库，详解索引原理(二)

有序数组

如果我们将mysql中表的数据以有序数组的⽅式存储在磁盘中，那么我们定位数据步骤

是：

1. 取出⽬标表的所有数据，存放在⼀个有序数组中

2. 如果⽬标表的数据量⾮常⼤，从磁盘中加载到内存中需要的内存也⾮常⼤

步骤取出所有数据耗费的io次数太多，步骤2耗费的内存空间太⼤，还有新增数据的时候，为了保证数组有序，插⼊数据会涉及到数组内部数据的移动，也是⽐较耗时的，显然⽤这种⽅式存储数据是不可取的。

220链表

链表相当于在每个节点上增加⼀些指针，可以和前⾯或者后⾯的节点连接起来，就像⼀列⽕车⼀样，每节车厢相当于⼀个节点，车厢内部可以存储数据，每个车厢和下⼀节车厢相连。

链表分为单链表和双向链表。

单链表

每个节点中有持有指向下⼀个节点的指针，只能按照⼀个⽅向遍历链表，结构如下：

//单项链表

class Node1{

private Object data;//存储数据

private Node1 nextNode;//指向下⼀个节点

}

双向链表

每个节点中两个指针，分别指向当前节点的上⼀个节点和下⼀个节点，结构如

下：

//双向链表

class Node2{

private Object data;//存储数据

private Node1 prevNode;//指向上⼀个节点

private Node1 nextNode;//指向下⼀个节点

}

链表的优点：

1. 可以快速定位到上⼀个或者下⼀个节点

2. 可以快速删除数据，只需改变指针的指向即可，这点⽐数组好

链表的缺点：

1. ⽆法向数组那样，通过下标随机访问数据2. 查找数据需从第⼀个节点开始遍历，不利于数据的查找，查找时间和⽆需数据类似，

需要全遍历，最差时间是O(N)

⼆叉查找树

⼆叉树是每个结点最多有两个⼦树的树结构，通常⼦树被称作“左⼦树”（left subtree）和“右⼦树”（right subtree）。⼆叉树常被⽤于实现⼆叉查找树和⼆叉堆。⼆叉树有如下特性：

1、每个结点都包含⼀个元素以及n个⼦树，这⾥0≤n≤2。 2、左⼦树和右⼦树是有顺序的，次序不能任意颠倒，左⼦树的值要⼩于⽗结点，右⼦树的值要⼤于⽗结点。

数组[20,10,5,15,30,25,35]使⽤⼆叉查找树存储如下：

每个节点上⾯有两个指针（left,rigth），可以通过这2个指针快速访问左右⼦节点，检索任何⼀个数据最多只需要访问3个节点，相当于访问了3次数据，时间为O(logN)，和⼆分法查找效率⼀样，查询数据还是⽐较快的。

但是如果我们插⼊数据是有序的，如[5,10,15,20,30,25,35]，那么结构就变成下⾯这样：

⼆叉树退化为了⼀个链表结构，查询数据最差就变为了O(N)。

⼆叉树的优缺点：

1. 查询数据的效率不稳定，若树左右⽐较平衡的时，最差情况为O(logN)，如果插⼊数据是有序的，退化为了链表，查询时间变成了O(N)2. 数据量⼤的情况下，会导致树的⾼度变⾼，如果每个节点对应磁盘的⼀个块来存储⼀

条数据，需io次数⼤幅增加，显然⽤此结构来存储数据是不可取的