存储结构

  关于与“存储结构”标题相近或相同的条目页，请见“存储结构 (消歧义)”。

注意：本页有Unihan新版汉字，这些字符可能会错误显示，详见Unicode扩展汉字。

存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构。它包括数据元素的表示和关系的表示。数据的存储结构是用计算机语言实现的逻辑结构，它依赖于计算机语言。数据的存储结构主要有顺序存储、链式存储、索引存储和散列存储。

存储结构在计算机科学中具有重要意义，因为它们直接影响数据的存取效率和存储空间的利用率。不同的存储结构适用于不同的应用场景，选择合适的存储结构可以显著提高程序的性能和可维护性。

存储结构

顺序存储

顺序存储是将逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。其优点是可以实现随机存取，每个元素占用最少的存储空间；缺点是插入和删除操作可能需要移动大量元素。

链式存储

链式存储不要求逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。其优点是不会出现碎片现象，能充分利用所有存储单元；缺点是每个元素因存储指针而占用额外的存储空间，访问速度较慢，因为需要遍历链表。

索引存储

索引存储在存储元素信息的同时，还建立附加的索引表。索引表中的每项称为索引项，索引项的一般形式是（关键字，地址）。其优点是检索速度快；缺点是附加的索引表额外占用存储空间。另外，增加和删除数据时也要修改索引表，因而会花费较多的时间。

散列存储

散列存储根据元素的关键字直接计算出该元素的存储地址，又称哈希（Hash）存储。其优点是检索、增加和删除结点的操作都很快；缺点是若散列函数不好，则可能出现元素存储单元的冲突，而解决冲突会增加时间和空间开销。

存储结构的发展历史和重要贡献者

顺序存储

顺序存储的概念可以追溯到早期的计算机科学发展时期，当时主要用于数组和矩阵的实现。John von Neumann 是顺序存储结构的早期贡献者之一，他在计算机体系结构方面的工作奠定了现代计算机科学的基础。顺序存储的早期应用包括磁鼓存储器和磁带存储器，这些技术在20世纪50年代和60年代被广泛使用。

链式存储

链式存储的概念由Allen Newell、Cliff Shaw和Herbert A. Simon在1956年提出，他们在开发逻辑理论家（Logic Theorist）时首次使用了链表。链表是一种基本的数据结构，广泛应用于各种计算机科学领域。链式存储的早期应用包括磁芯存储器，这种存储器在20世纪50年代末和60年代初被广泛使用。

索引存储

索引存储的概念在数据库管理系统的发展过程中逐渐形成。Edgar F. Codd在1970年提出了关系数据库模型，他的工作极大地推动了索引存储结构的发展。B树和B+树是索引存储的重要实现，由Rudolf Bayer和Edward M. McCreight在1972年提出。B树和B+树在数据库索引和文件系统中得到了广泛应用。

散列存储

散列存储的概念由H. P. Luhn在1953年提出，他在信息检索系统中首次使用了哈希函数。Donald Knuth在他的经典著作《计算机程序设计艺术》中详细讨论了散列存储，并对其理论基础做出了重要贡献。散列存储在数据库、文件系统和缓存系统中得到了广泛应用。

示例代码

顺序存储

以下是一个使用数组实现顺序存储的示例代码（Python）：

# 顺序存储示例：数组
array = [1, 2, 3, 4, 5]

# 插入元素
array.append(6)

# 删除元素
array.remove(3)

# 访问元素
print(array[2])  # 输出：3

链式存储

以下是一个使用链表实现链式存储的示例代码（Python）：

# 链式存储示例：链表
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

    def print_list(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# 使用链表
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.print_list()  # 输出：1 -> 2 -> 3 -> None

索引存储

以下是一个使用B树实现索引存储的示例代码（Python）：

# 索引存储示例：B树
class BTreeNode:
    def __init__(self, leaf=False):
        self.leaf = leaf
        self.keys = []
        self.children = []

class BTree:
    def __init__(self, t):
        self.root = BTreeNode(True)
        self.t = t

    def insert(self, k):
        root = self.root
        if len(root.keys) == (2 * self.t) - 1:
            temp = BTreeNode()
            self.root = temp
            temp.children.insert(0, root)
            self.split_child(temp, 0)
            self.insert_non_full(temp, k)
        else:
            self.insert_non_full(root, k)

    def insert_non_full(self, x, k):
        i = len(x.keys) - 1
        if x.leaf:
            x.keys.append((None, None))
            while i >= 0 and k < x.keys[i]:
                x.keys[i + 1] = x.keys[i]
                i -= 1
            x.keys[i + 1] = k
        else:
            while i >= 0 and k < x.keys[i]:
                i -= 1
            i += 1
            if len(x.children[i].keys) == (2 * self.t) - 1:
                self.split_child(x, i)
                if k > x.keys[i]:
                    i += 1
            self.insert_non_full(x.children[i], k)

    def split_child(self, x, i):
        t = self.t
        y = x.children[i]
        z = BTreeNode(y.leaf)
        x.children.insert(i + 1, z)
        x.keys.insert(i, y.keys[t - 1])
        z.keys = y.keys[t:(2 * t) - 1]
        y.keys = y.keys[0:t - 1]
        if not y.leaf:
            z.children = y.children[t:(2 * t)]
            y.children = y.children[0:t]

# 使用B树
btree = BTree(3)
btree.insert(10)
btree.insert(20)
btree.insert(5)
btree.insert(6)
btree.insert(12)
btree.insert(30)
btree.insert(7)
btree.insert(17)

散列存储

以下是一个使用哈希表实现散列存储的示例代码（Python）：

# 散列存储示例：哈希表
class HashTable:
    def __init__(self):
        self.size = 10
        self.table = [[] for _ in range(self.size)]

    def hash_function(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        hash_key = self.hash_function(key)
        key_exists = False
        bucket = self.table[hash_key]
        for i, kv in enumerate(bucket):
            k, v = kv
            if key == k:
                key_exists = True
                break
        if key_exists:
            bucket[i] = (key, value)
        else:
            bucket.append((key, value))

    def delete(self, key):
        hash_key = self.hash_function(key)
        bucket = self.table[hash_key]
        for i, kv in enumerate(bucket):
            k, v = kv
            if key == k:
                del bucket[i]
                break

    def search(self, key):
        hash_key = self.hash_function(key)
        bucket = self.table[hash_key]
        for k, v in bucket:
            if key == k:
                return v
        return None

# 使用哈希表
hash_table = HashTable()
hash_table.insert("key1", "value1")
hash_table.insert("key2", "value2")
print(hash_table.search("key1"))  # 输出：value1
hash_table.delete("key1")
print(hash_table.search("key1"))  # 输出：None