Best way to scale a tikzpicture with matrices

I am not sure, if I guessed all your packages right, I still get a font warning. However, you scaled most of your elements to the font size by chosing the unit em. Therefore to reduce size, you have to change the font size, which I did by saying \tiny in line 9:

\documentclass[]{beamer}
\usepackage{tikz}
\usetikzlibrary{matrix, positioning, arrows}

\begin{document}
\begin{frame}
\begin{figure}
\centering
\tiny
\begin{tikzpicture}[text depth=0.5ex, text height=2ex]
\matrix[matrix of math nodes, anchor=west, row sep=-\pgflinewidth, column sep=-\pgflinewidth, row 2/.style={minimum width=3em, nodes={rectangle, draw}}]
at (0.5,0) 
(mat1)
{
b_{n+1} \\
{} \\
};

\matrix[matrix of math nodes, ampersand replacement=\&, right=of mat1, row sep=-\pgflinewidth, column sep=-\pgflinewidth,row 2/.style={minimum width=3em, nodes={rectangle, draw}}] 
(mat2)
{
b_n \& \ldots \& b_{i+1} \& b_i \& b_{i-1} \& \ldots \& b_2 \& b_1 \\
{} \& {\hspace{1.5cm}} \& {} \& {} \& {} \& {\hspace{1.5cm}} \& {} \& {} \\
};
\node[above=0pt of mat2]
  (cellb) {$B_\mathcal{C}$};

\matrix[matrix of math nodes, anchor=west, row sep=-\pgflinewidth, column sep=-\pgflinewidth, row 1/.style={minimum width=3em, nodes={rectangle, draw}}]
at (0,-3) 
(mat3)
{
{} \\
b_{n+1} \\
};

\matrix[matrix of math nodes, ampersand replacement=\&, right=of mat3, row sep=-\pgflinewidth, column sep=-\pgflinewidth,row 1/.style={minimum width=3em, nodes={rectangle, draw}}] 
(mat4)
{
{} \& {\hspace{1.5cm}} \& {} \& {} \\
b_{m_{n- \delta}} \& \ldots \& b_{m_2} \& b_{m_1} \\
};
\node[below=0pt of mat4]
  (celld) {$B_U$};

\matrix[matrix of math nodes, ampersand replacement=\&, right=of mat4, row sep=-\pgflinewidth, column sep=-\pgflinewidth,row 1/.style={minimum width=3em, nodes={rectangle, draw}}] 
(mat5)
{
{} \& {\hspace{1.5cm}} \& {} \& {} \\
b_{k_{\delta}} \& \ldots \& b_{k_2} \& b_{k_1} \\
};
\node[below=0pt of mat5]
  (celle) {$B_R$};

\begin{scope}[shorten <= -2pt]
\draw[*->]
    (mat5-1-1.north) -- (mat2-2-1.south);
\draw[*->]
    (mat4-1-1.north) -- (mat2-2-3.south);
\draw[*->]
    (mat4-1-3.north) -- (mat2-2-4.south);
\draw[*->]
    (mat4-1-4.north) -- (mat2-2-8.south);
\draw[*->]
    (mat5-1-3.north) -- (mat2-2-5.south);
\draw[*->]
    (mat5-1-4.north) -- (mat2-2-7.south);
\end{scope}
\end{tikzpicture}
\end{figure}
\end{frame}
\end{document}

Or another option would be to scale the nodes and fonts of your tikz-picture as well by saying scale=0.7, every node/.style={scale=0.7}

\documentclass[]{beamer}
\usepackage{tikz}
\usetikzlibrary{matrix, positioning, arrows}

\begin{document}
\begin{frame}
\begin{figure}
\centering
\begin{tikzpicture}[text depth=0.5ex, text height=2ex, scale=0.7, every node/.style={scale=0.7}]
\matrix[matrix of math nodes, anchor=west, row sep=-\pgflinewidth, column sep=-\pgflinewidth, row 2/.style={minimum width=3em, nodes={rectangle, draw}}]
at (0.5,0) 
(mat1)
{
b_{n+1} \\
{} \\
};

\matrix[matrix of math nodes, ampersand replacement=\&, right=of mat1, row sep=-\pgflinewidth, column sep=-\pgflinewidth,row 2/.style={minimum width=3em, nodes={rectangle, draw}}] 
(mat2)
{
b_n \& \ldots \& b_{i+1} \& b_i \& b_{i-1} \& \ldots \& b_2 \& b_1 \\
{} \& {\hspace{1.5cm}} \& {} \& {} \& {} \& {\hspace{1.5cm}} \& {} \& {} \\
};
\node[above=0pt of mat2]
  (cellb) {$B_\mathcal{C}$};

\matrix[matrix of math nodes, anchor=west, row sep=-\pgflinewidth, column sep=-\pgflinewidth, row 1/.style={minimum width=3em, nodes={rectangle, draw}}]
at (0,-3) 
(mat3)
{
{} \\
b_{n+1} \\
};

\matrix[matrix of math nodes, ampersand replacement=\&, right=of mat3, row sep=-\pgflinewidth, column sep=-\pgflinewidth,row 1/.style={minimum width=3em, nodes={rectangle, draw}}] 
(mat4)
{
{} \& {\hspace{1.5cm}} \& {} \& {} \\
b_{m_{n- \delta}} \& \ldots \& b_{m_2} \& b_{m_1} \\
};
\node[below=0pt of mat4]
  (celld) {$B_U$};

\matrix[matrix of math nodes, ampersand replacement=\&, right=of mat4, row sep=-\pgflinewidth, column sep=-\pgflinewidth,row 1/.style={minimum width=3em, nodes={rectangle, draw}}] 
(mat5)
{
{} \& {\hspace{1.5cm}} \& {} \& {} \\
b_{k_{\delta}} \& \ldots \& b_{k_2} \& b_{k_1} \\
};
\node[below=0pt of mat5]
  (celle) {$B_R$};

\begin{scope}[shorten <= -2pt]
\draw[*->]
    (mat5-1-1.north) -- (mat2-2-1.south);
\draw[*->]
    (mat4-1-1.north) -- (mat2-2-3.south);
\draw[*->]
    (mat4-1-3.north) -- (mat2-2-4.south);
\draw[*->]
    (mat4-1-4.north) -- (mat2-2-8.south);
\draw[*->]
    (mat5-1-3.north) -- (mat2-2-5.south);
\draw[*->]
    (mat5-1-4.north) -- (mat2-2-7.south);
\end{scope}
\end{tikzpicture}
\end{figure}
\end{frame}
\end{document}

you can scale your figure by using transform canvas={scale=0.7}for example. as the following

\documentclass[]{beamer}
\usepackage{tikz}
\usetikzlibrary{matrix, positioning, arrows}
\begin{document}
\begin{frame}
\begin{figure}
\centering
\begin{tikzpicture}[transform canvas={scale=0.7}]
\matrix[matrix of math nodes, anchor=west, row sep=-\pgflinewidth, column sep=-\pgflinewidth, row 2/.style={minimum width=3em, nodes={rectangle, draw}}]
at (-6,0) 
(mat1)
{
b_{n+1} \\
{} \\
};

\matrix[matrix of math nodes, ampersand replacement=\&, right=of mat1, row sep=-\pgflinewidth, column sep=-\pgflinewidth,row 2/.style={minimum width=3em, nodes={rectangle, draw}}] 
(mat2)
{
b_n \& \ldots \& b_{i+1} \& b_i \& b_{i-1} \& \ldots \& b_2 \& b_1 \\
{} \& {\hspace{1.5cm}} \& {} \& {} \& {} \& {\hspace{1.5cm}} \& {} \& {} \\
};
\node[above=0pt of mat2]
  (cellb) {$B_\mathcal{C}$};

\matrix[matrix of math nodes, anchor=west, row sep=-\pgflinewidth, column sep=-\pgflinewidth, row 1/.style={minimum width=3em, nodes={rectangle, draw}}]
at (-6.5,-3) 
(mat3)
{
{} \\
b_{n+1} \\
};

\matrix[matrix of math nodes, ampersand replacement=\&, right=of mat3, row sep=-\pgflinewidth, column sep=-\pgflinewidth,row 1/.style={minimum width=3em, nodes={rectangle, draw}}] 
(mat4)
{
{} \& {\hspace{1.5cm}} \& {} \& {} \\
b_{m_{n- \delta}} \& \ldots \& b_{m_2} \& b_{m_1} \\
};
\node[below=0pt of mat4]
  (celld) {$B_U$};

\matrix[matrix of math nodes, ampersand replacement=\&, right=of mat4, row sep=-\pgflinewidth, column sep=-\pgflinewidth,row 1/.style={minimum width=3em, nodes={rectangle, draw}}] 
(mat5)
{
{} \& {\hspace{1.5cm}} \& {} \& {} \\
b_{k_{\delta}} \& \ldots \& b_{k_2} \& b_{k_1} \\
};
\node[below=0pt of mat5]
  (celle) {$B_R$};

\begin{scope}[shorten <= -2pt]
\draw[*->]
    (mat5-1-1.north) -- (mat2-2-1.south);
\draw[*->]
    (mat4-1-1.north) -- (mat2-2-3.south);
\draw[*->]
    (mat4-1-3.north) -- (mat2-2-4.south);
\draw[*->]
    (mat4-1-4.north) -- (mat2-2-8.south);
\draw[*->]
    (mat5-1-3.north) -- (mat2-2-5.south);
\draw[*->]
    (mat5-1-4.north) -- (mat2-2-7.south);
\end{scope}
\end{tikzpicture}
\end{figure}
\end{frame}
\end{document}