Này Habr! Tôi trình bày với bạn chú ý bản dịch của bài báo
"Cơ sở dữ liệu quan hệ hoạt động như thế nào".

Khi nói đến cơ sở dữ liệu quan hệ, tôi không thể không nghĩ rằng còn thiếu một cái gì đó. Chúng được sử dụng ở mọi nơi. Có sẵn nhiều cơ sở dữ liệu khác nhau, từ SQLite nhỏ và hữu ích đến Teradata mạnh mẽ. Nhưng chỉ có một số bài viết giải thích cách hoạt động của cơ sở dữ liệu. Bạn có thể tự tìm kiếm bằng cách sử dụng "howdoesarelationaldatabasework" để xem có bao nhiêu kết quả. Hơn nữa, những bài viết này rất ngắn. Nếu bạn đang tìm kiếm các công nghệ mới nhất (BigData, NoSQL hoặc JavaScript), bạn sẽ tìm thấy các bài viết chuyên sâu hơn giải thích cách chúng hoạt động.

Có phải cơ sở dữ liệu quan hệ đã quá cũ và quá nhàm chán để được giải thích bên ngoài các khóa học đại học, tài liệu nghiên cứu và sách?

Là một nhà phát triển, tôi ghét sử dụng thứ gì đó mà tôi không hiểu. Và nếu cơ sở dữ liệu đã được sử dụng hơn 40 năm thì chắc chắn phải có lý do. Trong nhiều năm, tôi đã dành hàng trăm giờ để thực sự hiểu những chiếc hộp đen kỳ lạ mà tôi sử dụng hàng ngày này. Cơ sở dữ liệu quan hệ rất thú vị bởi vì họ dựa trên các khái niệm hữu ích và có thể tái sử dụng. Nếu bạn quan tâm đến việc tìm hiểu cơ sở dữ liệu nhưng chưa bao giờ có thời gian hoặc ý định nghiên cứu sâu về chủ đề rộng lớn này, bạn nên thưởng thức bài viết này.

Mặc dù tiêu đề của bài viết này là rõ ràng, Mục đích của bài viết này không phải là hiểu cách sử dụng cơ sở dữ liệu. do đó, bạn hẳn đã biết cách viết một yêu cầu kết nối đơn giản và các truy vấn cơ bản NGUYÊN; nếu không bạn có thể không hiểu bài viết này. Đó là điều duy nhất bạn cần biết, tôi sẽ giải thích phần còn lại.

Tôi sẽ bắt đầu với một số kiến thức cơ bản về khoa học máy tính, chẳng hạn như độ phức tạp về thời gian của thuật toán (BigO). Tôi biết một số bạn ghét khái niệm này, nhưng nếu không có nó, bạn sẽ không thể hiểu được sự phức tạp bên trong cơ sở dữ liệu. Vì đây là một chủ đề lớn, Tôi sẽ tập trung vào điều tôi nghĩ là quan trọng: cơ sở dữ liệu xử lý như thế nào SQL cuộc điều tra. Tôi sẽ chỉ giới thiệu khái niệm cơ sở dữ liệu cơ bảnđể đến cuối bài viết, bạn sẽ biết được những gì đang diễn ra bên dưới.

Vì đây là một bài viết dài và mang tính kỹ thuật, liên quan đến nhiều thuật toán và cấu trúc dữ liệu nên bạn hãy dành thời gian đọc qua nó. Một số khái niệm có thể khó hiểu; bạn có thể bỏ qua chúng mà vẫn nắm được ý tưởng chung.

Để các bạn hiểu rõ hơn, bài viết này được chia thành 3 phần:

Tổng quan về các thành phần cơ sở dữ liệu cấp thấp và cấp cao
Tổng quan về quy trình tối ưu hóa truy vấn
Tổng quan về giao dịch và quản lý vùng đệm

Trở lại vấn đề cơ bản

Nhiều năm trước (trong một thiên hà rất xa...), các nhà phát triển phải biết chính xác số lượng hoạt động mà họ đang mã hóa. Họ thuộc lòng các thuật toán và cấu trúc dữ liệu vì họ không thể lãng phí CPU và bộ nhớ của những chiếc máy tính chậm chạp của mình.

Trong phần này, tôi sẽ nhắc bạn về một số khái niệm này vì chúng rất cần thiết để hiểu cơ sở dữ liệu. Tôi cũng sẽ giới thiệu khái niệm chỉ mục cơ sở dữ liệu.

O(1) so với O(n2)

Ngày nay, nhiều nhà phát triển không quan tâm đến độ phức tạp về thời gian của thuật toán... và họ đã đúng!

Nhưng khi bạn đang xử lý nhiều dữ liệu (tôi không nói đến hàng nghìn) hoặc nếu bạn đang gặp khó khăn trong tính bằng mili giây, việc hiểu khái niệm này trở nên quan trọng. Và như bạn có thể tưởng tượng, cơ sở dữ liệu phải giải quyết cả hai tình huống! Tôi sẽ không bắt bạn tốn nhiều thời gian hơn mức cần thiết để hiểu rõ vấn đề. Điều này sẽ giúp chúng ta hiểu khái niệm tối ưu hóa dựa trên chi phí sau này (chi phí dựa tối ưu hóa).

Khái niệm

Độ phức tạp thời gian của thuật toán được sử dụng để xem thuật toán sẽ mất bao lâu để hoàn thành một lượng dữ liệu nhất định. Để mô tả độ phức tạp này, chúng tôi sử dụng ký hiệu toán học big O. Ký hiệu này được sử dụng với hàm mô tả số lượng phép toán mà một thuật toán cần cho một số lượng đầu vào nhất định.

Ví dụ: khi tôi nói "thuật toán này có độ phức tạp O(some_function())", điều đó có nghĩa là thuật toán yêu cầu các thao tác some_function(a_certain_amount_of_data) để xử lý một lượng dữ liệu nhất định.

Trong trường hợp này, Vấn đề không phải là lượng dữ liệu**, nếu không thì ** số lượng thao tác tăng lên như thế nào khi khối lượng dữ liệu tăng lên. Độ phức tạp về thời gian không cung cấp số lượng thao tác chính xác nhưng là một cách tốt để ước tính thời gian thực hiện.

Trong biểu đồ này, bạn có thể thấy số lượng thao tác so với lượng dữ liệu đầu vào cho các loại độ phức tạp về thời gian của thuật toán khác nhau. Tôi đã sử dụng thang đo logarit để hiển thị chúng. Nói cách khác, lượng dữ liệu tăng nhanh từ 1 đến 1 tỷ, chúng ta có thể thấy rằng:

O(1) hoặc độ phức tạp không đổi không đổi (nếu không nó sẽ không được gọi là độ phức tạp không đổi).
O(đăng nhập(n)) vẫn ở mức thấp ngay cả với hàng tỷ dữ liệu.
Khó khăn nhất - O(n2), trong đó số lượng hoạt động tăng nhanh.
Hai biến chứng còn lại cũng tăng lên nhanh chóng.

Ví dụ

Với một lượng dữ liệu nhỏ, sự khác biệt giữa O(1) và O(n2) là không đáng kể. Ví dụ: giả sử bạn có một thuật toán cần xử lý 2000 phần tử.

Thuật toán O(1) sẽ tốn của bạn 1 thao tác
Thuật toán O(log(n)) sẽ khiến bạn mất 7 thao tác
Thuật toán O(n) sẽ tiêu tốn của bạn 2 thao tác
Thuật toán O(n*log(n)) sẽ tiêu tốn của bạn 14 thao tác
Thuật toán O(n2) sẽ tiêu tốn của bạn 4 thao tác

Sự khác biệt giữa O(1) và O(n2) có vẻ lớn (4 triệu thao tác) nhưng bạn sẽ mất tối đa 2 mili giây, chỉ cần chớp mắt một chút. Thật vậy, các bộ xử lý hiện đại có thể xử lý hàng trăm triệu phép tính mỗi giây. Đây là lý do tại sao hiệu suất và tối ưu hóa không phải là vấn đề trong nhiều dự án CNTT.

Như tôi đã nói, điều quan trọng là phải biết khái niệm này khi làm việc với lượng dữ liệu khổng lồ. Nếu lần này thuật toán phải xử lý 1 phần tử (không nhiều đối với cơ sở dữ liệu):

Thuật toán O(1) sẽ tốn của bạn 1 thao tác
Thuật toán O(log(n)) sẽ khiến bạn mất 14 thao tác
Thuật toán O(n) sẽ tiêu tốn của bạn 1 thao tác
Thuật toán O(n*log(n)) sẽ tiêu tốn của bạn 14 thao tác
Thuật toán O(n2) sẽ tiêu tốn của bạn 1 thao tác

Tôi chưa tính toán, nhưng tôi muốn nói rằng với thuật toán O(n2) bạn có thời gian để uống một ly cà phê (thậm chí là hai!). Nếu bạn thêm số 0 khác vào khối lượng dữ liệu, bạn sẽ có thời gian để chợp mắt.

Hãy đi sâu hơn

Đối với thông tin của bạn:

Tra cứu bảng băm tốt sẽ tìm thấy một phần tử trong O(1).
Tìm kiếm một cây cân bằng tốt sẽ cho kết quả là O(log(n)).
Tìm kiếm một mảng cho kết quả là O(n).
Các thuật toán sắp xếp tốt nhất có độ phức tạp O(n*log(n)).
Thuật toán sắp xếp kém có độ phức tạp O(n2).

Lưu ý: Trong các phần sau chúng ta sẽ thấy các thuật toán và cấu trúc dữ liệu này.

Có một số loại độ phức tạp về thời gian của thuật toán:

kịch bản trung bình
kịch bản hay nhất
và tình huống xấu nhất

Độ phức tạp về thời gian thường là trường hợp xấu nhất.

Tôi chỉ nói về độ phức tạp về thời gian của thuật toán, nhưng độ phức tạp cũng áp dụng cho:

mức tiêu thụ bộ nhớ của thuật toán
thuật toán tiêu thụ I/O đĩa

Tất nhiên, có những biến chứng nặng hơn n2, ví dụ:

n4: khủng khiếp quá! Một số thuật toán được đề cập có độ phức tạp này.
3n: chuyện này còn tệ hơn nữa! Một trong những thuật toán chúng ta sẽ thấy ở giữa bài viết này có độ phức tạp như vậy (và nó thực sự được sử dụng trong nhiều cơ sở dữ liệu).
giai thừa n: bạn sẽ không bao giờ nhận được kết quả ngay cả với một lượng nhỏ dữ liệu.
nn: Nếu bạn gặp phải sự phức tạp này thì bạn nên tự hỏi liệu đây có thực sự là lĩnh vực hoạt động của bạn không...

Lưu ý: Tôi không cung cấp cho bạn định nghĩa thực tế về ký hiệu chữ O lớn, chỉ là một ý tưởng. Bạn có thể đọc bài viết này tại Wikipedia cho định nghĩa thực (tiệm cận).

Hợp nhấtSắp xếp

Bạn làm gì khi cần sắp xếp một bộ sưu tập? Cái gì? Bạn gọi hàm sắp xếp()... Được rồi, câu trả lời hay... Nhưng đối với cơ sở dữ liệu, bạn phải hiểu cách hoạt động của hàm sắp xếp() này.

Có một số thuật toán sắp xếp tốt, vì vậy tôi sẽ tập trung vào điều quan trọng nhất: sắp xếp hợp nhất. Bạn có thể không hiểu tại sao việc sắp xếp dữ liệu lại hữu ích ngay bây giờ, nhưng bạn nên hiểu sau phần tối ưu hóa truy vấn. Hơn nữa, việc hiểu cách sắp xếp hợp nhất sẽ giúp chúng ta sau này hiểu được thao tác nối cơ sở dữ liệu phổ biến được gọi là hợp nhất tham gia (hiệp hội sáp nhập).

Hợp nhất

Giống như nhiều thuật toán hữu ích, sắp xếp hợp nhất dựa vào một thủ thuật: kết hợp 2 mảng đã sắp xếp có kích thước N/2 thành một mảng được sắp xếp N phần tử chỉ tốn N thao tác. Hoạt động này được gọi là hợp nhất.

Hãy xem điều này có nghĩa gì bằng một ví dụ đơn giản:

Hình này cho thấy để xây dựng mảng 8 phần tử được sắp xếp cuối cùng, bạn chỉ cần lặp lại một lần trên 2 mảng 4 phần tử. Vì cả hai mảng 4 phần tử đều đã được sắp xếp:

1) bạn so sánh cả hai phần tử hiện tại trong hai mảng (ở đầu hiện tại = đầu tiên)
2) sau đó lấy cái nhỏ nhất đưa vào mảng 8 phần tử
3) và di chuyển đến phần tử tiếp theo trong mảng nơi bạn lấy phần tử nhỏ nhất
và lặp lại 1,2,3 cho đến khi bạn đạt được phần tử cuối cùng của một trong các mảng.
Sau đó bạn lấy các phần tử còn lại của mảng kia ghép vào mảng 8 phần tử.

Điều này hiệu quả vì cả hai mảng 4 phần tử đều được sắp xếp và do đó bạn không cần phải "quay lại" các mảng đó.

Bây giờ chúng ta đã hiểu thủ thuật, đây là mã giả của tôi để hợp nhất:

array mergeSort(array a)
   if(length(a)==1)
      return a[0];
   end if

   //recursive calls
   [left_array right_array] := split_into_2_equally_sized_arrays(a);
   array new_left_array := mergeSort(left_array);
   array new_right_array := mergeSort(right_array);

   //merging the 2 small ordered arrays into a big one
   array result := merge(new_left_array,new_right_array);
   return result;

Sắp xếp hợp nhất chia một bài toán thành các bài toán nhỏ hơn rồi tìm kết quả của các bài toán nhỏ hơn để thu được kết quả của bài toán ban đầu (lưu ý: loại thuật toán này được gọi là chia để trị). Nếu bạn không hiểu thuật toán này, đừng lo lắng; Tôi đã không hiểu nó khi lần đầu tiên tôi nhìn thấy nó. Nếu nó có thể giúp bạn, tôi thấy thuật toán này là thuật toán hai giai đoạn:

Giai đoạn phân chia, trong đó mảng được chia thành các mảng nhỏ hơn
Giai đoạn sắp xếp là nơi các mảng nhỏ được kết hợp (sử dụng phép hợp) để tạo thành một mảng lớn hơn.

Giai đoạn phân chia

Ở giai đoạn phân chia, mảng được chia thành các mảng đơn nhất theo 3 bước. Số bước chính thức là log(N) (vì N=8, log(N) = 3).

Làm thế nào để tôi biết điều này?

Tôi là thiên tài! Trong một từ - toán học. Ý tưởng là mỗi bước chia kích thước của mảng ban đầu cho 2. Số bước là số lần bạn có thể chia mảng ban đầu thành hai. Đây là định nghĩa chính xác của logarit (cơ số 2).

Giai đoạn sắp xếp

Trong giai đoạn sắp xếp, bạn bắt đầu với mảng đơn nhất (một phần tử). Trong mỗi bước bạn áp dụng nhiều thao tác hợp nhất và tổng chi phí là N = 8 thao tác:

Trong giai đoạn đầu tiên, bạn có 4 lần hợp nhất, mỗi lần tốn 2 thao tác
Ở bước thứ hai, bạn có 2 lần hợp nhất, mỗi lần tốn 4 thao tác
Ở bước thứ ba, bạn có 1 lần hợp nhất tốn 8 thao tác

Vì có các bước log(N), tổng chi phí N * hoạt động log(N).

Ưu điểm của sắp xếp hợp nhất

Tại sao thuật toán này lại mạnh mẽ đến vậy?

Tại vì:

Bạn có thể thay đổi nó để giảm dung lượng bộ nhớ để không tạo mảng mới mà trực tiếp sửa đổi mảng đầu vào.

Lưu ý: loại thuật toán này được gọi là in-nơi (sắp xếp không cần thêm bộ nhớ).

Bạn có thể thay đổi nó để sử dụng dung lượng ổ đĩa và một lượng nhỏ bộ nhớ cùng lúc mà không phải chịu chi phí I/O ổ đĩa đáng kể. Ý tưởng là chỉ tải vào bộ nhớ những phần hiện đang được xử lý. Điều này rất quan trọng khi bạn cần sắp xếp một bảng nhiều gigabyte chỉ với bộ nhớ đệm 100 megabyte.

Lưu ý: loại thuật toán này được gọi là sắp xếp bên ngoài.

Bạn có thể thay đổi nó để chạy trên nhiều tiến trình/luồng/máy chủ.

Ví dụ: sắp xếp hợp nhất phân tán là một trong những thành phần chính Hadoop (là một cấu trúc trong dữ liệu lớn).

Thuật toán này có thể biến chì thành vàng (thật đấy!).

Thuật toán sắp xếp này được sử dụng trong hầu hết (nếu không phải tất cả) cơ sở dữ liệu, nhưng nó không phải là cơ sở dữ liệu duy nhất. Nếu bạn muốn biết thêm, bạn có thể đọc cái này công việc nghiên cứu, thảo luận về ưu và nhược điểm của các thuật toán sắp xếp cơ sở dữ liệu phổ biến.

Mảng, cây và bảng băm

Bây giờ chúng ta đã hiểu ý tưởng về độ phức tạp và sắp xếp thời gian, tôi sẽ kể cho bạn nghe về 3 cấu trúc dữ liệu. Điều này quan trọng bởi vì họ là nền tảng của cơ sở dữ liệu hiện đại. Tôi cũng sẽ giới thiệu khái niệm chỉ mục cơ sở dữ liệu.

Mảng

Mảng hai chiều là cấu trúc dữ liệu đơn giản nhất. Một bảng có thể được coi như một mảng. Ví dụ:

Mảng 2 chiều này là một bảng có các hàng và cột:

Mỗi dòng đại diện cho một thực thể
Cột lưu trữ các thuộc tính mô tả thực thể.
Mỗi cột lưu trữ dữ liệu thuộc một loại cụ thể (số nguyên, chuỗi, ngày ...).

Điều này thuận tiện cho việc lưu trữ và hiển thị dữ liệu, tuy nhiên, khi bạn cần tìm một giá trị cụ thể thì điều này không phù hợp.

Ví dụ: nếu bạn muốn tìm tất cả những người làm việc ở Vương quốc Anh, bạn cần xem từng hàng để xác định xem hàng đó có thuộc về Vương quốc Anh hay không. Bạn sẽ mất N giao dịchĐâu N - số dòng, không tệ, nhưng có cách nào nhanh hơn không? Bây giờ là lúc chúng ta làm quen với cây cối.

Lưu ý: Hầu hết các cơ sở dữ liệu hiện đại đều cung cấp các mảng mở rộng để lưu trữ các bảng một cách hiệu quả: các bảng được tổ chức theo đống và các bảng được tổ chức theo chỉ mục. Nhưng điều này không làm thay đổi vấn đề tìm nhanh một điều kiện cụ thể trong một nhóm cột.

Cây cơ sở dữ liệu và chỉ mục

Cây tìm kiếm nhị phân là cây nhị phân có thuộc tính đặc biệt, khóa tại mỗi nút phải là:

lớn hơn tất cả các khóa được lưu trữ trong cây con bên trái
ít hơn tất cả các khóa được lưu trữ trong cây con bên phải

Hãy xem điều này có nghĩa gì một cách trực quan

Ý tưởng

Cây này có N = 15 phần tử. Giả sử tôi đang tìm kiếm 208:

Tôi bắt đầu từ gốc có khóa là 136. Vì 136<208, tôi nhìn vào cây con bên phải của nút 136.
398>208 do đó tôi đang xem cây con bên trái của nút 398
250>208 do đó tôi đang xem cây con bên trái của nút 250
200<208, do đó tôi đang xem cây con bên phải của nút 200. Nhưng 200 không có cây con bên phải, giá trị không tồn tại (vì nếu tồn tại thì nó sẽ nằm ở cây con bên phải 200).

Bây giờ giả sử tôi đang tìm 40

Tôi bắt đầu từ gốc có khóa là 136. Vì 136 > 40, tôi nhìn vào cây con bên trái của nút 136.
80 > 40, do đó tôi đang xem cây con bên trái của nút 80
40= 40, nút tồn tại. Tôi truy xuất ID hàng bên trong nút (không hiển thị trong hình) và tìm trong bảng để tìm ID hàng đã cho.
Việc biết ID hàng cho phép tôi biết chính xác dữ liệu ở đâu trong bảng để tôi có thể truy xuất dữ liệu đó ngay lập tức.

Cuối cùng, cả hai tìm kiếm đều khiến tôi mất số cấp độ bên trong cây. Nếu bạn đọc kỹ phần về sắp xếp hợp nhất, bạn sẽ thấy rằng có các mức log(N). Hóa ra, nhật ký chi phí tìm kiếm(N), không tệ!

Hãy quay lại vấn đề của chúng ta

Nhưng điều này rất trừu tượng nên hãy quay lại vấn đề của chúng ta. Thay vì một số nguyên đơn giản, hãy tưởng tượng một chuỗi đại diện cho quốc gia của ai đó trong bảng trước. Giả sử bạn có một cây chứa trường "quốc gia" (cột 3) của bảng:

Nếu bạn muốn biết ai làm việc ở Anh
bạn nhìn vào cái cây để lấy nút đại diện cho Vương quốc Anh
bên trong "UKnode" bạn sẽ tìm thấy vị trí của hồ sơ công nhân Vương quốc Anh.

Việc tìm kiếm này sẽ tốn các thao tác log(N) thay vì N thao tác nếu bạn sử dụng trực tiếp mảng. Những gì bạn vừa trình bày là chỉ mục cơ sở dữ liệu.

Bạn có thể xây dựng cây chỉ mục cho bất kỳ nhóm trường nào (chuỗi, số, 2 dòng, số và chuỗi, ngày tháng...) miễn là bạn có hàm so sánh khóa (tức là nhóm trường) để bạn có thể đặt thứ tự giữa các phím (đó là trường hợp của bất kỳ loại cơ bản nào trong cơ sở dữ liệu).

Chỉ số cây B+

Mặc dù cây này hoạt động tốt để nhận được một giá trị cụ thể nhưng có một vấn đề LỚN khi bạn cần lấy nhiều phần tử giữa hai giá trị. Điều này sẽ tốn O(N) vì bạn sẽ phải xem xét từng nút trong cây và kiểm tra xem nó có nằm giữa hai giá trị này hay không (ví dụ: với việc duyệt cây theo thứ tự). Hơn nữa, thao tác này không thân thiện với I/O của đĩa vì bạn phải đọc toàn bộ cây. Chúng ta cần tìm cách thực hiện hiệu quả yêu cầu phạm vi. Để giải quyết vấn đề này, cơ sở dữ liệu hiện đại sử dụng phiên bản sửa đổi của cây trước đó có tên là B+Tree. Trong cây B+tree:

chỉ các nút thấp nhất (lá) lưu trữ thông tin (vị trí các hàng trong bảng liên quan)
các nút còn lại ở đây để định tuyến đến đúng nút trong quá trình tìm kiếm.

Như bạn có thể thấy, có nhiều nút hơn ở đây (hai lần). Thật vậy, bạn có các nút bổ sung, "nút quyết định", sẽ giúp bạn tìm đúng nút (lưu trữ vị trí của các hàng trong bảng liên kết). Nhưng độ phức tạp của tìm kiếm vẫn là O(log(N)) (chỉ còn một cấp độ nữa). Sự khác biệt lớn đó là các nút ở cấp độ thấp hơn được kết nối với các nút kế nhiệm của chúng.

Với B+Cây này, nếu bạn đang tìm kiếm các giá trị trong khoảng từ 40 đến 100:

Bạn chỉ cần tìm 40 (hoặc giá trị gần nhất sau 40 nếu 40 không tồn tại) giống như bạn đã làm với cây trước đó.
Sau đó thu thập 40 người thừa kế bằng cách sử dụng liên kết người thừa kế trực tiếp cho đến khi bạn đạt 100.

Giả sử bạn tìm thấy M phần kế tiếp và cây có N nút. Tìm log(N) chi phí nút cụ thể như cây trước đó. Nhưng một khi bạn có được nút này, bạn sẽ nhận được M phần tử kế thừa trong M hoạt động có tham chiếu đến phần tử kế vị của chúng. Tìm kiếm này chỉ tốn M+log(N) so với N phép toán trên cây trước đó. Hơn nữa, bạn không phải đọc toàn bộ cây (chỉ các nút M+log(N), nghĩa là sử dụng ít đĩa hơn. Nếu M nhỏ (ví dụ 200 hàng) và N lớn (1 hàng), sẽ có sự khác biệt LỚN.

Nhưng có những vấn đề mới ở đây (một lần nữa!). Nếu bạn thêm hoặc xóa một hàng trong cơ sở dữ liệu (và do đó trong chỉ mục B+Cây được liên kết):

bạn phải duy trì trật tự giữa các nút bên trong Cây B+, nếu không bạn sẽ không thể tìm thấy các nút bên trong cây chưa được sắp xếp.
bạn phải giữ số cấp tối thiểu có thể có trong B+Cây, nếu không thì độ phức tạp về thời gian O(log(N)) sẽ trở thành O(N).

Nói cách khác, B+Tree phải có tính tự sắp xếp và cân bằng. May mắn thay, điều này có thể thực hiện được nhờ các thao tác xóa và chèn thông minh. Nhưng điều này phải trả giá: việc chèn và xóa trong cây B+ có giá O(log(N)). Đó là lý do tại sao một số bạn đã nghe điều đó sử dụng quá nhiều chỉ mục không phải là một ý tưởng hay. Thật sự, bạn đang làm chậm quá trình chèn/cập nhật/xóa nhanh một hàng trong bảngvì cơ sở dữ liệu cần cập nhật các chỉ mục của bảng bằng thao tác O(log(N)) đắt tiền cho mỗi chỉ mục. Hơn nữa, việc thêm chỉ mục có nghĩa là khối lượng công việc nhiều hơn cho người quản lý giao dịch (sẽ được mô tả ở cuối bài viết).

Để biết thêm chi tiết, bạn có thể xem bài viết Wikipedia về B+Cây. Nếu bạn muốn có ví dụ về cách triển khai B+Tree trong cơ sở dữ liệu, hãy xem bài viết này и bài viết này từ một nhà phát triển MySQL hàng đầu. Cả hai đều tập trung vào cách InnoDB (công cụ MySQL) xử lý các chỉ mục.

Lưu ý: Một độc giả đã nói với tôi rằng, do tối ưu hóa ở mức độ thấp nên cây B+ phải hoàn toàn cân bằng.

bảng băm

Cấu trúc dữ liệu quan trọng cuối cùng của chúng ta là bảng băm. Điều này rất hữu ích khi bạn muốn tra cứu nhanh các giá trị. Hơn nữa, việc hiểu bảng băm sẽ giúp chúng ta sau này hiểu được thao tác nối cơ sở dữ liệu phổ biến được gọi là nối băm ( tham gia băm). Cấu trúc dữ liệu này cũng được cơ sở dữ liệu sử dụng để lưu trữ một số thứ bên trong (ví dụ: khóa bàn hoặc vùng đệm, chúng ta sẽ thấy cả hai khái niệm này sau).

Bảng băm là cấu trúc dữ liệu giúp tìm nhanh một phần tử bằng khóa của nó. Để xây dựng bảng băm bạn cần xác định:

chìa khóa cho các phần tử của bạn
hàm băm cho các phím. Các giá trị băm khóa được tính toán cung cấp vị trí của các phần tử (được gọi là phân đoạn ).
chức năng so sánh các phím. Khi bạn đã tìm thấy phân khúc chính xác, bạn phải tìm phần tử bạn đang tìm kiếm trong phân khúc đó bằng cách sử dụng phép so sánh này.

Ví dụ đơn giản

Hãy lấy một ví dụ rõ ràng:

Bảng băm này có 10 phân đoạn. Vì lười nên chỉ vẽ 5 đoạn nhưng biết bạn thông minh nên tôi để bạn tự vẽ 5 đoạn còn lại. Tôi đã sử dụng hàm băm modulo 10 của khóa. Nói cách khác, tôi chỉ lưu trữ chữ số cuối cùng của khóa phần tử để tìm phân đoạn của nó:

nếu chữ số cuối cùng là 0 thì phần tử rơi vào phân đoạn 0,
nếu chữ số cuối cùng là 1 thì phần tử rơi vào phân đoạn 1,
nếu chữ số cuối cùng là 2 thì phần tử rơi vào vùng 2,
...

Hàm so sánh tôi sử dụng chỉ đơn giản là sự bằng nhau giữa hai số nguyên.

Giả sử bạn muốn lấy phần tử 78:

Bảng băm tính mã băm cho 78, tức là 8.
Bảng băm nhìn vào phân đoạn 8 và phần tử đầu tiên nó tìm thấy là 78.
Cô ấy trả lại món hàng 78 cho bạn
Chi phí tìm kiếm chỉ có 2 thao tác (một để tính giá trị băm và một để tra cứu phần tử trong phân đoạn).

Bây giờ giả sử bạn muốn lấy phần tử 59:

Bảng băm tính mã băm cho 59, tức là 9.
Bảng băm tìm kiếm trong phân đoạn 9, phần tử đầu tiên được tìm thấy là 99. Vì 99!=59, phần tử 99 không phải là phần tử hợp lệ.
Sử dụng logic tương tự, phần tử thứ hai (9), phần tử thứ ba (79), ..., phần tử cuối cùng (29) được lấy.
Không tìm thấy phần tử.
Chi phí tìm kiếm 7 thao tác.

Hàm băm tốt

Như bạn có thể thấy, tùy thuộc vào giá trị bạn đang tìm kiếm mà chi phí sẽ không giống nhau!

Nếu bây giờ tôi thay đổi hàm băm modulo 1 của khóa (tức là lấy 000 chữ số cuối), thì lần tra cứu thứ hai chỉ tốn 000 thao tác vì không có phần tử nào trong phân đoạn 6. Thách thức thực sự là tìm ra một hàm băm tốt có thể tạo ra các nhóm chứa một số lượng phần tử rất nhỏ..

Trong ví dụ của tôi, việc tìm một hàm băm tốt rất dễ dàng. Nhưng đây là một ví dụ đơn giản, việc tìm một hàm băm tốt sẽ khó hơn khi khóa là:

chuỗi (ví dụ - họ)
2 dòng (ví dụ - họ và tên)
2 dòng và ngày (ví dụ - họ, tên và ngày sinh)
...

Với hàm băm tốt, việc tra cứu bảng băm có giá O(1).

Mảng và bảng băm

Tại sao không sử dụng một mảng?

Ừm, câu hỏi hay.

Bảng băm có thể được tải một phần vào bộ nhớvà các phân đoạn còn lại có thể vẫn còn trên đĩa.
Với một mảng, bạn phải sử dụng không gian liền kề trong bộ nhớ. Nếu bạn đang tải một bảng lớn rất khó để tìm đủ không gian liên tục.
Đối với bảng băm, bạn có thể chọn khóa bạn muốn (ví dụ: quốc gia và họ của người).

Để biết thêm thông tin, bạn có thể đọc bài viết về JavaBản đồ băm, đây là cách triển khai hiệu quả của bảng băm; bạn không cần phải hiểu Java mới có thể hiểu được các khái niệm được đề cập trong bài viết này.

Nguồn: www.habr.com

Cơ sở dữ liệu quan hệ hoạt động như thế nào (Phần 1)