有序数组
如果我们将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次数⼤幅增加,显然⽤此结构来存储数据是不可取的