CFSDN nhấn mạnh vào giá trị tạo ra nguồn mở và chúng tôi cam kết xây dựng nền tảng chia sẻ tài nguyên để mọi nhân viên CNTT có thể tìm thấy thế giới tuyệt vời của bạn tại đây.

Bài viết trên blog CFSDN Cơ chế chỉ mục MySQL (Phải biết dành cho lập trình viên) này được tác giả sưu tầm và biên soạn. Nếu các bạn quan tâm đến bài viết này thì nhớ like nhé.

1. Chỉ số là gì?

  。

Định nghĩa chính thức của MySQL về chỉ mục là: Index (Index) là cấu trúc dữ liệu giúp MySQL lấy dữ liệu một cách hiệu quả và cấu trúc dữ liệu được MYSQL sử dụng là: B+tree.

Ở đây tôi khuyên bạn nên đọc cuốn sách "Sách để hiểu sâu về hệ thống máy tính".

1.1 Nguyên tắc địa phương.

Các truy cập chương trình và dữ liệu có xu hướng phân cụm. Trong một khoảng thời gian, chỉ một phần nhỏ trong số chúng được sử dụng. Thông tin sẽ được sử dụng trong tương lai gần có thể sẽ gần với địa chỉ không gian của thông tin hiện đang được sử dụng. vị trí không gian), hoặc mã chương trình và dữ liệu đã được truy cập gần đây rất có thể sẽ sớm được truy cập lại (được gọi là vị trí tạm thời).

1.2 Đọc trước đĩa.

Độ dài của phần đọc trước nói chung là bội số nguyên của một trang. Một trang là một khối bộ nhớ logic. Hệ điều hành thường chia bộ nhớ chính và vùng lưu trữ đĩa thành các khối có kích thước bằng nhau liên tiếp. trang (trong nhiều Trong hệ điều hành, kích thước trang thường là 4K) và bộ nhớ chính và dữ liệu trao đổi đĩa theo đơn vị trang.

1.3 Giới thiệu.

Khi sử dụng cơ sở dữ liệu, truy vấn cơ sở dữ liệu thường là một trong những chức năng quan trọng nhất của cơ sở dữ liệu. Nhưng mỗi thuật toán tìm kiếm chỉ có thể áp dụng cho những cấu trúc dữ liệu cụ thể.

• Ví dụ: tìm kiếm nhị phân yêu cầu dữ liệu được truy xuất phải theo thứ tự
• Tìm kiếm cây nhị phân chỉ có thể áp dụng cho cây tìm kiếm nhị phân, nhưng bản thân cấu trúc tổ chức của dữ liệu không thể đáp ứng đầy đủ các cấu trúc dữ liệu khác nhau (ví dụ: về mặt lý thuyết không thể sắp xếp cả hai cột theo thứ tự cùng một lúc), do đó giữa các dữ liệu Ngoài ra, hệ thống cơ sở dữ liệu còn duy trì các cấu trúc dữ liệu đáp ứng các thuật toán tìm kiếm cụ thể. Các cấu trúc dữ liệu này tham chiếu (trỏ tới) dữ liệu theo một cách nào đó, nhờ đó các thuật toán tìm kiếm nâng cao có thể được triển khai trên các cấu trúc dữ liệu này. Cấu trúc dữ liệu này là một chỉ mục. Các chỉ mục thường được lưu trữ trên đĩa dưới dạng tệp và việc truy xuất chỉ mục yêu cầu các thao tác I/O của đĩa. Do đó, chỉ số quan trọng nhất để đánh giá chất lượng của cấu trúc dữ liệu dưới dạng chỉ mục là độ phức tạp tiệm cận của số lượng thao tác I/O trên đĩa trong quá trình tìm kiếm.

1. Index là một cấu trúc dữ liệu giúp MYSQL lấy dữ liệu một cách hiệu quả.
2. Chỉ mục được lưu trữ trong hệ thống tập tin
3. Dạng lưu trữ file của chỉ mục có liên quan đến công cụ lưu trữ
4. Cấu trúc file chỉ mục: hàm băm, cây nhị phân, cây B, cây B+

2. Phân loại chỉ số

  。

2.1 băm 。

Có một tệp dữ liệu mysql ở đây có hai cột, Id và tên. Nếu chúng ta lưu trữ nó ở định dạng băm (bảng băm), chúng ta chỉ cần tính giá trị băm của một cột nhất định và lấy modulo theo độ dài của mảng. có thể lấy các vị trí chỉ số dưới từ 0 đến 7n Trong trường hợp này, hiệu quả thực sự tương đối cao, nhưng việc sử dụng bảng băm để lưu trữ nó có một số nhược điểm nhất định:

1. Nếu bạn sử dụng bộ lưu trữ băm, bạn cần thêm tất cả các tệp dữ liệu vào bộ nhớ, việc này sẽ tiêu tốn nhiều dung lượng bộ nhớ hơn.
2. Nếu tất cả các truy vấn đều là truy vấn tương đương thì việc băm thực sự rất nhanh. Tuy nhiên, trong môi trường doanh nghiệp hoặc làm việc thực tế, cần phải tìm kiếm nhiều dữ liệu hơn trong một phạm vi thay vì các truy vấn tương đương, vì băm không phù hợp nên không được sử dụng trong. mysql. Định dạng lưu trữ băm không được chọn 2.2 Cây nhị phân

Định dạng chỉ mục:

Đối với cây, có một chuỗi các cập nhật và lỗi. Đừng nhìn vào cấu trúc ngay từ đầu. Đầu tiên, hãy hiểu cây là gì. Cây bao gồm một gốc và n nhánh. có nhiều nhánh cây (nhiều phần tử) thì hiệu quả tìm kiếm lúc này sẽ tương đối thấp nên có cây nhị phân. Tại sao cây nhị phân lại dễ sử dụng hơn? Vì cây nhị phân có hai nhánh nhưng hai nhánh sẽ dẫn đến. một hiệu ứng, nghĩa là, mỗi khi chúng ta Khi tìm kiếm dữ liệu cũng tương tự như tìm kiếm nhị phân, nhưng cây nhị phân cũng có nhược điểm riêng. Bạn có thể xem định dạng chỉ mục của cây nhị phân trong hình trên sẽ ngắn hơn (chỉ cần ngắn hơn). đọc ba lần). Và nút bên phải. Nó sẽ dài hơn nhiều (cần đọc năm lần), điều này sẽ khiến độ sâu của cây càng sâu. Mỗi khi đọc một nút của cây thì IO càng cao. IO, điều này sẽ ảnh hưởng đến hiệu quả đọc dữ liệu của chúng ta, do đó có (cây nhị phân cân bằng) và (cây đỏ đen) .

Cây nhị phân cân bằng: Để duy trì sự cân bằng, độ chênh lệch giữa chiều cao của cây con bên trái và cây con bên phải không thể lớn hơn 1, nhưng nó không phù hợp với định dạng trên của chúng ta vì đã vượt quá 1, nhưng cây AVL cũng có vấn đề Số lần điều chỉnh quá thường xuyên. Nó bao gồm một thao tác xoay, một vòng quay trái và một vòng quay phải để duy trì sự cân bằng, cần có N vòng quay như vậy thực sự rất lãng phí thời gian. việc thêm hoặc xóa được thực hiện. Khi thực hiện việc này, nó phải trải qua N vòng quay, điều này quá kém hiệu quả.

Mình giới thiệu cho các bạn một trang web có thể xem trực tiếp quá trình hoạt động của cây AVL. Học sinh nào chưa hiểu có thể vào xem rất sinh động: Cây AVL (Cây tìm kiếm nhị phân cân bằng).

Cây đỏ đen: Bản thân nó cũng là một cây cân bằng, nhưng nó đánh đổi ở giữa, tức là nó mất một phần hiệu suất cân bằng, nhưng vẫn duy trì sự cân bằng tương đối, tức là chiều cao của cây. cây con dài nhất, miễn là không vượt quá cây con ngắn nhất. Hai lần là đủ. Đồng thời, nó đưa ra thông tin nút đỏ và nút đen trong cây đỏ-đen. Trong AVL Cây có chuyển động xoay để duy trì sự cân bằng, trong khi cây đỏ đen có chuyển động xoay và thay đổi màu sắc để duy trì sự cân bằng. và xóa dữ liệu. Mặc dù mất đi một số hiệu suất nhưng nó vẫn là một cây cân bằng. Vì là cây cân bằng nên cây con dài nhất của nó không quá hai lần cây con ngắn nhất, nghĩa là nếu cây con ngắn nhất là 4. , khi đó cây con dài nhất là 8 nên khi chúng ta tìm kiếm dữ liệu không phải là tìm kiếm nhị phân và hiệu quả sẽ thấp hơn.

Dù là cây nhị phân hay cây đỏ đen thì số lượng IO sẽ tăng lên do độ sâu của cây quá sâu sẽ ảnh hưởng đến hiệu quả đọc dữ liệu. Điều quan trọng nhất là giảm IO.

IO là một nút cổ chai trong ngành CNTT của chúng tôi. Một là IO đĩa và hai là IO mạng. Với tư cách là nhà phát triển phần mềm, chúng tôi không có cách nào để điều chỉnh nút cổ chai phần cứng. Chúng tôi chỉ có thể giảm khối lượng IO của mình khỏi chương trình. một là giảm số lượng IO, và hai là giảm số lượng IO từ hai cái này. Ví dụ, để giải quyết nó ở một số khía cạnh, chúng ta thường đọc dữ liệu 10 lần, nhưng bây giờ chúng ta chỉ cần đọc một lần, do đó lượng IO giảm đi 10 lần. Ban đầu chúng ta cần đọc 1 MB dữ liệu, nhưng bây giờ. chúng tôi chỉ cần đọc 1KB dữ liệu. Đây cũng là lý do tại sao chúng tôi không khuyên bạn nên sử dụng select khi viết câu lệnh truy vấn mysql. * từ, bởi vì một truy vấn như vậy sẽ truy vấn N nhiều trường. Ban đầu tôi chỉ muốn có hai trường, nhưng tôi được cung cấp 30 trường. Điều này sẽ làm tăng số lượng IO, vì vậy chúng tôi sẽ xem xét chỉ mục có thể tăng bao nhiêu lần. , do đó kết quả sau dẫn đến cây B của chúng ta.

2.3 Cây B.

Đặc điểm của cây B:

• Tất cả các giá trị khóa được phân phối khắp cây
• Việc tìm kiếm có thể kết thúc tại một nút không phải là lá và việc tìm kiếm được thực hiện trong toàn bộ tập hợp từ khóa. Hiệu suất gần giống với tìm kiếm nhị phân.
• Mỗi nút có tối đa m cây con
• Nút gốc có ít nhất 2 cây con
• Nút nhánh có ít nhất m/2 cây con (tất cả các nút nhánh ngoại trừ nút gốc và nút lá)
• Tất cả các nút lá đều ở cùng cấp độ. Mỗi nút có thể có tối đa m-1 khóa và được sắp xếp theo thứ tự tăng dần.

Mô tả cấu trúc cây B:

Mô tả sơ đồ ví dụ: Mỗi nút chiếm một khối đĩa. Có hai từ khóa theo thứ tự tăng dần trên một nút và ba con trỏ tới nút gốc của cây con. Các con trỏ lưu trữ địa chỉ của khối đĩa nơi đặt hai nút con. từ khóa Ba trường phạm vi được chia tương ứng với các trường phạm vi của dữ liệu của cây con được trỏ bởi ba con trỏ. Lấy nút gốc làm cột, từ khóa là 16 và 34, phạm vi dữ liệu của cây con được trỏ bởi con trỏ p1 nhỏ hơn 16, phạm vi dữ liệu của cây con được trỏ bởi con trỏ P2 là 16-34 và dữ liệu phạm vi của cây con được trỏ bởi con trỏ P3 lớn hơn 34 Từ khóa tìm kiếm (28) quá trình:

• Tìm khối đĩa 1 theo nút và đọc bộ nhớ [thao tác I/O đĩa lần đầu tiên]
• So sánh từ khóa 28 để tìm con trỏ P2 của khối đĩa 1 trong khoảng (16,34)
• Tìm khối đĩa 3 theo con trỏ P2 và đọc nó vào bộ nhớ [thao tác I/O đĩa lần thứ 2]
• So sánh từ khóa 28 trong khoảng (25,31) và tìm con trỏ P2 của khối đĩa 3
• Tìm khối đĩa 8 theo con trỏ P2, đọc bộ nhớ, [thao tác I/O đĩa lần thứ 3]
• Từ khóa 28 được tìm thấy trong danh sách từ khóa ở khối đĩa 8

thiếu sót:

• Mỗi nút có một khóa và cũng chứa dữ liệu, đồng thời không gian lưu trữ của mỗi trang bị hạn chế. Nếu dữ liệu tương đối lớn thì số lượng khóa được lưu trữ trong mỗi nút sẽ ít hơn.
• Khi lượng dữ liệu được lưu trữ lớn sẽ dẫn đến độ sâu lớn hơn và tăng số lượng IO đĩa trong quá trình truy vấn, do đó ảnh hưởng đến hiệu suất truy vấn.

2,4 cây B+.

B+Tree là sự tối ưu hóa dựa trên BTree, với những thay đổi sau:

• Mỗi nút của Cây B+ có thể chứa nhiều nút hơn. Lý do đầu tiên là để giảm chiều cao của cây. Lý do thứ hai là thay đổi phạm vi dữ liệu thành nhiều khoảng. lấy nhanh hơn
• Các nút không phải lá lưu trữ khóa (đĩa 1, 2 và 3 đều lưu trữ khóa) và các nút lá lưu trữ khóa và dữ liệu.
• Hai con trỏ của các nút lá được kết nối với nhau (phù hợp với đặc tính đọc trước của đĩa). Hiệu suất truy vấn tuần tự cao hơn. Nếu không có nút nào khác trong khối đĩa hiện tại thì đó là nút lá và ngược lại. ngược lại, nó là một nút không có lá.

Sơ đồ cấu trúc:

Lưu ý: Có hai con trỏ đầu trên B+Cây, một trỏ đến nút gốc và con trỏ còn lại trỏ đến nút lá có khóa nhỏ nhất và có một cấu trúc vòng chuỗi giữa tất cả các nút lá (tức là các nút dữ liệu), do đó, nó B+Tree có thể thực hiện hai thao tác truy vấn, một là tìm kiếm theo phạm vi và tìm kiếm phân trang cho khóa chính và hai là tìm kiếm ngẫu nhiên bắt đầu từ nút gốc.

3. Công cụ lưu trữ Mysql

  。

3.1 mysql innoDB (các nút lá đặt dữ liệu trực tiếp).

3.1 mysql innoDB (các nút lá đặt dữ liệu trực tiếp).

Các bản ghi hàng tương ứng được lưu trữ.

1. InnoDB tạo chỉ mục trên khóa chính thông qua cấu trúc B+tree, sau đó lưu trữ các bản ghi trong các nút lá. Nếu không có khóa chính thì một khóa duy nhất sẽ được chọn. row_id gồm 6 chữ số sẽ được tạo làm khóa chính.

2. Nếu khóa để tạo chỉ mục là một trường khác thì khóa chính của bản ghi sẽ được lưu trong nút lá và sau đó bản ghi tương ứng sẽ được tìm thấy thông qua chỉ mục khóa chính.

Tạo một chỉ mục trên name.

ID được lưu trữ trong cột tên và khóa và dữ liệu tương ứng được tìm thấy thông qua ID.

3.1 mysql MyISAM 。

0X0022 sau đây thực sự là địa chỉ. Nó hiển thị địa chỉ của chúng tôi dựa trên ID của chúng tôi và sau đó sử dụng địa chỉ để tìm dữ liệu tương ứng với bảng tương ứng.

4. Phân loại chỉ số

  。

Có năm loại chỉ mục mysql: chỉ mục khóa chính, chỉ mục duy nhất, chỉ mục thông thường và chỉ mục toàn văn bản và chỉ mục kết hợp. Bằng cách thêm chỉ mục vào các trường, bạn có thể tăng tốc độ đọc dữ liệu và cải thiện khả năng xử lý đồng thời cũng như khả năng chống căng thẳng của dự án.

• Chỉ mục khóa chính: > Khóa chính là một chỉ mục duy nhất, nhưng nó phải được chỉ định là KHÓA CHÍNH. Mỗi bảng chỉ có thể có một khóa chính.
• Chỉ mục duy nhất > Tất cả các giá trị trong cột chỉ mục chỉ có thể xuất hiện một lần, nghĩa là chúng phải là duy nhất và giá trị có thể trống
• Chỉ mục thông thường > Loại chỉ mục cơ bản, giá trị có thể trống, không có giới hạn về tính duy nhất
• Chỉ mục toàn văn bản > Loại chỉ mục của chỉ mục toàn văn bản là FULLTEXT. Chỉ mục toàn văn bản có thể được tạo trên các cột kiểu varchar, char và văn bản.
• Chỉ mục kết hợp > Chỉ mục bao gồm nhiều giá trị cột, được sử dụng cụ thể cho tìm kiếm kết hợp

5. Công cụ lưu trữ MySQL

  。

bản tóm tắt.

Khi tôi viết bài này, liên tục có những tin nhắn từ nhóm công ty Xiaonong, vì có những vấn đề trong dự án mà tôi cần giải quyết. Đó là cơ chế lập chỉ mục mysql ngày nay.

Địa chỉ gốc: https://mp.weixin.qq.com/s/GS7F1ABzLWrj0PqRS2R3EA.

Cuối cùng, bài viết về cơ chế lập chỉ mục MySQL (lập trình viên phải biết) kết thúc tại đây. Nếu bạn muốn biết thêm về cơ chế lập chỉ mục MySQL (lập trình viên phải biết), vui lòng tìm kiếm các bài viết về CFSDN hoặc tiếp tục duyệt các bài viết liên quan. mong mọi người sẽ ủng hộ blog của mình trong tương lai nhé! .