存儲結構

關於與「存儲結構」標題相近或相同的條目頁，請見「存儲結構 (消歧義)」。

注意：本頁有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